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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
0 Y; ?; W2 {$ |% W/ T' D/ j4 vand
                       x1>=0; x2>=0; x3>=0

当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

. Z  q. w7 }( `3 y- ~, y6 F5 G用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

4 u2 Y, m. C. {7 w" h# b' m
7 ?/ w4 ]; t  u+ e根据 s.t.可知 :
  S4 S: n  v0 L/ f, j) X; m0<=x1<=5;
0<=x2<=2;
/ w9 P; @& B' T( @0 X0<=x3<=3;

+ L0 w# _# I& H动态规划过程如下：
: @; z/ }; v$ T1 d  ]* B
int dp[6][3][4], maxn, tmp, ans;

' J* o- D& t5 f3 f; a, ]6 F+ jmemset(dp,0,sizoef(dp));

for (i=0;i<=5;i++)
3 l( u& F' j9 n0 G2 c    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
            maxn=0;
            if (i>0)
2 Y/ B8 u" v  h' @            {
" S% r+ r) x# b. \6 \                tmp=dp[i-1][j][k]+3;
7 ~8 N( x- H; j* g4 X1 N9 e                if (tmp>maxn)
+ s; g. A/ L) t7 b. x/ u5 N1 Z                    maxn=tmp;
            }
            if (j>0)
4 k( s7 m" `- x) m1 U            {
                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
# J2 e1 U3 C. G& u                    maxn=tmp;
6 g2 I; b1 Q+ `            }
$ R2 S4 ~* n$ p, w7 e, N0 g            if (k>0)
$ p# r6 ?9 f! p            {
                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
                    maxn=tmp;
# W* X" H" g& t3 R' P            }
8 p+ `( y0 U0 x" Q7 b) m5 D            dp[j][k]=maxn;
( Z. r9 b. l7 e        }

ans=0;
1 h/ ~* I" ?/ p/ t5 ?7 I+ dfor (i=0;i<=5;i++)
, ~1 |! S% F3 i' w( z. U    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
# f4 [- N: O- s% [2 b9 c1 g3 A            if (i+3*j+2*k>6)
                continue;
            if (i+j>5)
% J2 o: c4 A, E0 R! W: j                continue;
            tmp=dp[j][k];
            if (k>0)
, ~" g$ E0 {4 q& F" r1 X                tmp-=6;
, L. p- x' I3 l' J# j6 r            if (tmp>ans)
" S2 ^- p5 P& g5 ?8 [& X$ c4 z! R' H6 T9 [                ans=tmp;
        }
printf("%d\n", ans);
ans极为目标函数的最大值。

jerrybond6

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

gaoshanliu水