有没有哪位高人会用动态规划来解线性规划的题？ 附题一道

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
7 J7 ^& k! p8 J) F/ c4 w0 dand
                       x1>=0; x2>=0; x3>=0
( y2 b0 ~6 y& k( _* h! _: t( o( G
当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
! [9 q+ k$ g( G3 u2 S/ |
0 U1 b& I# m) N3 V% ]用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

gaoshanliu水

jerrybond6

网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

jerrybond6

4 _6 K2 p9 v) |5 r+ M根据 s.t.可知 :
0<=x1<=5;
0<=x2<=2;
/ r1 ?1 j/ r, b0<=x3<=3;

" Z5 G/ g6 s* u4 m% A动态规划过程如下：

int dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));

8 C. r! b' \. d8 k+ S) \& P8 P: Ifor (i=0;i<=5;i++)
9 V! c* }6 B' z    for (j=0;j<=2;j++)
* }( e; F5 J! E6 u: }& _        for (k=0;k<=3;k++)
        {
( n, E! W2 V* ^            maxn=0;
# J5 R# {1 y* S" Y1 ?            if (i>0)
+ l  r+ S( \4 [3 R            {
& Q+ ]* m/ F' W7 E- L3 }2 X7 l: v                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
                    maxn=tmp;
  @' y8 o( E2 C# d: O            }
            if (j>0)
$ j( w0 z- T$ G- q            {
3 R2 o% ~1 Y$ S+ M) L+ Q) s                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
( q6 m% f' v: y8 c: b" J                    maxn=tmp;
; W! ]' ]' j; c$ r            }
            if (k>0)
            {
                tmp=dp[j][k-1]+6;
+ h1 w& w; q, \! q6 g( y. Y                if (tmp>maxn)
" _7 W4 x5 B. X1 f                    maxn=tmp;
$ O5 J; s7 i  X8 Q3 u% z" w            }
            dp[j][k]=maxn;
2 c8 n5 V0 o" f$ {3 V        }

' L1 ~7 S8 \5 b. e5 j: z; R4 pans=0;
for (i=0;i<=5;i++)
! @/ h5 w# J) Y2 a+ V9 v+ x    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
. i; y, `6 o1 N6 D; V: X5 x        {
% z- T* l* S! q3 W% i            if (i+3*j+2*k>6)
                continue;
7 v. C( U1 v" g" s+ Q$ m            if (i+j>5)
1 V8 `; Z2 `7 K( A( l0 n                continue;
            tmp=dp[j][k];
            if (k>0)
* j  \+ J! f2 l7 a8 F) g                tmp-=6;
            if (tmp>ans)
                ans=tmp;
3 `9 E8 ^& h$ r        }
printf("%d\n", ans);
% y+ I: d+ _" \+ hans极为目标函数的最大值。
: C- b$ P) F  }- T+ J1 t0 w/ r