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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
: L) S$ `5 Z+ O* u0 P                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
1 @( Y' x9 L" t- s5 E) |4 |and
7 y& v/ l3 v" w                       x1>=0; x2>=0; x3>=0

, W8 v+ X. p: Y: b3 d当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
2 ?4 \1 h8 h6 h: ]: F+ Y
  y% O3 f5 T+ d0 i用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

8 ]. q) d0 W" ], H9 L
根据 s.t.可知 :
! r& G* F8 ]/ P! S" T$ d0<=x1<=5;
' }: F8 G: S% b$ H7 Z0<=x2<=2;
9 n; p9 l2 Z+ p0 Y+ a& ]2 g0<=x3<=3;
- d: Z4 B/ T" i; w( W. H
动态规划过程如下：

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

memset(dp,0,sizoef(dp));
0 V/ e0 d/ L* a( z$ _! l  S
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
            maxn=0;
& |- C  V7 R( J( ?3 R  g, j            if (i>0)
            {
& j" Z  d# [3 N( ~9 b                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
                    maxn=tmp;
            }
$ t) D! G. G# Z% k/ {. |7 p            if (j>0)
            {
                tmp=dp[j-1][k]+7;
/ f' [, R, e4 j. Q& O                if (tmp>maxn)
2 F+ b2 n- i8 l$ R; t! m. D                    maxn=tmp;
            }
            if (k>0)
            {
                tmp=dp[j][k-1]+6;
. o7 s) |! @, Y4 m2 s                if (tmp>maxn)
$ u0 B, ?  `- d- f( i; n, i                    maxn=tmp;
            }
2 V* L2 l: H6 J& H  N& f$ t$ ?" R            dp[j][k]=maxn;
        }

9 {1 U8 D" }- B% o( f7 oans=0;
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
: K! P9 N+ L4 C% p        for (k=0;k<=3;k++)
        {
1 o2 h+ y5 ~* R1 \& ]4 f# O6 D            if (i+3*j+2*k>6)
                continue;
7 r0 ]1 v/ I' G! t9 Q- _: S( G0 X% Y            if (i+j>5)
- o  Q! M3 N' \4 h                continue;
: k, ^& _/ ^" i1 R            tmp=dp[j][k];
5 ~! G6 [2 [. F8 ~$ s& |6 e" Y; F; m7 F3 ?            if (k>0)
/ p6 l8 ?- g2 P                tmp-=6;
            if (tmp>ans)
                ans=tmp;
$ }$ A, F8 v2 s5 p2 A5 y4 S5 U        }
& B. Z+ R8 i' r4 }% f9 [printf("%d\n", ans);
ans极为目标函数的最大值。
& j. Z6 o; U+ f) @& t. o( j5 d

jerrybond6

1 Z. X0 |, m3 e0 ^' E. r7 o8 z/ n
网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水