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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
and
                       x1>=0; x2>=0; x3>=0
. L+ s! M* I. ]9 X% U5 b. x% I
3 W) J7 M& t8 _/ P$ O% V5 w9 L当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

5 G3 q( P9 q/ M$ V用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
7 @! p4 x$ r( Q

jerrybond6

4 {$ i# t& H& E6 C6 }/ ^根据 s.t.可知 :
0<=x1<=5;
! P1 b0 u7 @: L6 p3 |& u, [0<=x2<=2;
. J$ L6 ^9 ?& v0<=x3<=3;

5 f$ S1 N2 J2 \/ A6 [6 V动态规划过程如下：

+ D( c5 t/ n2 R; u8 Q5 ~* d+ uint dp[6][3][4], maxn, tmp, ans;

0 V; D$ ~- e  f+ cmemset(dp,0,sizoef(dp));

for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
1 k$ j: O$ j5 y) @8 y' @1 U        {
            maxn=0;
            if (i>0)
* G3 i2 F# C6 B9 o* x: d            {
) B0 a9 g* P: C, K2 L6 O6 f! `                tmp=dp[i-1][j][k]+3;
( M. R/ `6 a% j/ h, r% _                if (tmp>maxn)
' r: `, H+ [9 K/ B2 P* R5 q                    maxn=tmp;
            }
            if (j>0)
* y) E0 c1 J( e* {            {
                tmp=dp[j-1][k]+7;
& q" l4 d+ r. U$ t                if (tmp>maxn)
! G0 m& x" J8 s! ], r& L                    maxn=tmp;
- P* H( R9 C4 S$ r2 |" v. ]            }
            if (k>0)
            {
, L5 j! v6 Q3 [) v' q                tmp=dp[j][k-1]+6;
. J& r1 J& z! S5 [4 v2 [0 V                if (tmp>maxn)
8 {( V, ^; ~5 R& S# S" Y                    maxn=tmp;
0 i; p0 Y6 H% b" x            }
            dp[j][k]=maxn;
        }

ans=0;
for (i=0;i<=5;i++)
2 C: \5 `2 y7 ?+ P& p    for (j=0;j<=2;j++)
1 d3 o: t1 z. s3 v1 O6 Y        for (k=0;k<=3;k++)
        {
            if (i+3*j+2*k>6)
                continue;
            if (i+j>5)
                continue;
3 l+ {- A0 m5 P: g; `( c+ j            tmp=dp[j][k];
3 }3 P2 l- q. n: n: u            if (k>0)
- @+ {+ w( ]& ?- O4 G5 x% G                tmp-=6;
" l+ B9 P9 z" o1 g: x8 t            if (tmp>ans)
                ans=tmp;
        }
printf("%d\n", ans);
  f" I5 Q" N, w* w/ U0 Xans极为目标函数的最大值。
# o& B7 y9 W$ F: R% t. G% d5 T

jerrybond6

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

gaoshanliu水