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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
( ^9 \4 u* @5 r) V4 e3 t                       x1 + x2 <= 5
and
. T( e% ~8 @, w# a: @                       x1>=0; x2>=0; x3>=0
' U2 i2 `/ e- b6 n- |3 R/ V
9 `% U* ]5 S+ H" s7 d( J当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
( l* r5 \9 _' p' ?( M/ W' W

jerrybond6

8 ~; a  s, G1 n+ c( Z( c0 ~根据 s.t.可知 :
  Y0 E+ H5 h. v8 h8 {6 O0<=x1<=5;
& Y0 r: A2 J) l" L% B& q9 P0<=x2<=2;
/ c/ h) }% C- o9 `- j, f$ d3 r' h7 y) U0<=x3<=3;
, Q( h  z9 H  h6 ^7 m( f
. j9 R0 s9 F1 A动态规划过程如下：

4 G; u  b: u5 Xint dp[6][3][4], maxn, tmp, ans;
, z  h# w+ e& B/ K4 E4 H
* k$ S. H5 J- V7 M# _6 xmemset(dp,0,sizoef(dp));
; n+ h; Q4 t& H6 M
* Z% f: n- h8 k/ yfor (i=0;i<=5;i++)
5 n3 G1 \2 G) I. i8 U    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
            maxn=0;
3 s- ]1 Q" e1 y& X            if (i>0)
5 j& f% M0 C( y7 D1 X            {
                tmp=dp[i-1][j][k]+3;
5 y  K# i' g1 E& y/ e! n                if (tmp>maxn)
                    maxn=tmp;
" [/ m; E# x  E7 Y; Q; s: t7 P            }
! g" [( R3 T: i( C0 `            if (j>0)
1 n) w, P9 z$ t, n6 x& d- i# _            {
                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
                    maxn=tmp;
            }
7 R0 d( G) F9 v( L3 i/ Y7 j5 r            if (k>0)
            {
& T: }& q6 v; G0 N; A; v                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
                    maxn=tmp;
& t* I" F0 ~# o- ?$ U+ O            }
            dp[j][k]=maxn;
        }
  s" A1 A2 o: J4 `/ @3 Q
ans=0;
for (i=0;i<=5;i++)
8 o, e% J6 [& a- o$ n% C    for (j=0;j<=2;j++)
5 S- L2 t5 m7 O* {: i9 e        for (k=0;k<=3;k++)
; D! |: J: H0 d8 ^2 q        {
/ M. [5 ~0 Z  C7 x/ l8 O# r            if (i+3*j+2*k>6)
$ S/ v5 p) M/ I* x                continue;
            if (i+j>5)
. W; a) S4 G. x5 m, k/ K2 v                continue;
3 w" L6 S8 w, M1 O            tmp=dp[j][k];
, B2 e) s( o& \$ q7 k5 ]$ I4 B7 V            if (k>0)
                tmp-=6;
            if (tmp>ans)
  o0 q7 s' x; l                ans=tmp;
7 g2 R) }, r8 y% u; m        }
printf("%d\n", ans);
- E+ _6 I2 ^7 N4 nans极为目标函数的最大值。
7 c, Q0 A/ k3 P) S5 O

jerrybond6

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

gaoshanliu水