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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
7 F8 T% T$ }6 Z% {) U5 C5 F                       x1 + x2 <= 5
and
                       x1>=0; x2>=0; x3>=0
/ q# a, H. C; \$ L3 i3 Z
当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

, R! y; g2 W( n$ p用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

根据 s.t.可知 :
( y8 e# }3 y; a0<=x1<=5;
0<=x2<=2;
. z6 ~; D. \5 k0<=x3<=3;
3 {& ~+ Y' k6 l" f/ X' A
+ M. ]5 H4 r1 R: t( N6 [1 W动态规划过程如下：
' c: x7 Z) ~  Q4 l2 R! }
* B' {* g. k4 D7 [4 X. u1 Q: C5 fint dp[6][3][4], maxn, tmp, ans;
  l( }' a6 h5 x1 Y( }
memset(dp,0,sizoef(dp));

for (i=0;i<=5;i++)
3 Q4 Z9 |; c- S' D, V    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
: K. O* N: ?. O5 R7 Y        {
            maxn=0;
            if (i>0)
            {
8 p9 ~8 Y8 c' Z- p8 Z                tmp=dp[i-1][j][k]+3;
5 h# j5 ~% n! @2 ~; b                if (tmp>maxn)
7 N1 Q& {* G9 w                    maxn=tmp;
; Z0 F: Y! I) {. \) c6 f            }
0 E9 D6 D. x# |1 y( A            if (j>0)
            {
                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
* r' ~% x8 a. m) \' l) B                    maxn=tmp;
            }
9 y/ e/ Y0 U' c, M0 J            if (k>0)
0 d" O; \+ Q  u+ [7 A( p7 E2 U            {
( n0 I5 s' z# L9 L$ f8 D8 |                tmp=dp[j][k-1]+6;
$ ^8 w) [5 }4 X* g$ ^                if (tmp>maxn)
1 r# j: ]7 E' i& I                    maxn=tmp;
            }
* \' x* J# g$ Z0 N' q* O. O            dp[j][k]=maxn;
        }
3 \" Y: q0 q% Z
, [2 ^  I8 g7 [! Xans=0;
for (i=0;i<=5;i++)
7 s- C, b; p4 v0 F    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
' I! U$ S$ O+ ]) {        {
- [5 A2 g0 d* l* [2 N2 U1 j            if (i+3*j+2*k>6)
  C, r& N3 u4 B: v* O6 X                continue;
) D; @  D1 Y5 C4 U- `7 K            if (i+j>5)
5 D0 I( s3 W4 b$ l7 D! t) I                continue;
            tmp=dp[j][k];
            if (k>0)
  V- O% f% e) c1 m: j5 N                tmp-=6;
# L% B2 X& p( G' |% u+ P            if (tmp>ans)
                ans=tmp;
0 w3 Q4 \% Y& k) m4 }        }
4 i9 x8 e/ v' A- J  ?printf("%d\n", ans);
ans极为目标函数的最大值。
4 q+ _6 e/ s' t6 E+ _0 n+ S

jerrybond6

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

gaoshanliu水