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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
  Z! p# q9 ^6 \) M                       x1 + 3 x2 + 2 x3  <= 6
: O6 z% g+ S! @                       x1 + x2 <= 5
. a- T4 s  c0 E7 N9 Y) x: r3 Qand
                       x1>=0; x2>=0; x3>=0

6 _! M; J* X! f6 s: L: v当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
! c* w* Z! k7 k+ ?: I+ t7 Q" a
" s. \3 j  [1 E& ~6 s用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
0 ?& k6 v' x7 Z2 g5 o$ `3 X2 |

jerrybond6

% `9 [6 z3 {; `& c% x+ C% A根据 s.t.可知 :
. J& @+ M- Y- v. e, Z0<=x1<=5;
$ g8 f7 h2 n, i0<=x2<=2;
0<=x3<=3;

动态规划过程如下：

int dp[6][3][4], maxn, tmp, ans;
" A8 S' K* b, o! u4 {
memset(dp,0,sizoef(dp));
: v* l& Q0 Z- G; B! N& G
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
6 _  U7 T& f8 |* n* S9 O8 U2 [$ y        {
            maxn=0;
            if (i>0)
/ |( |% S1 p' {! j: e, \            {
                tmp=dp[i-1][j][k]+3;
0 A3 ?. }" M6 |; u) A* S7 q! {                if (tmp>maxn)
                    maxn=tmp;
            }
; W* ]0 D( \) D& _6 p/ `0 r            if (j>0)
6 Z( V. P3 ?6 N& y8 h            {
& q2 C- e1 `% j                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
* j: _; X8 X# H2 Q( ~0 N                    maxn=tmp;
            }
            if (k>0)
            {
  ]& w6 a0 B% [$ J% z                tmp=dp[j][k-1]+6;
: H# ]4 v9 R$ ?( k: R                if (tmp>maxn)
$ ]9 o" \2 X; s. w( ]                    maxn=tmp;
            }
) j0 O. U; [" \1 u! ?! a/ V            dp[j][k]=maxn;
        }
1 p; _$ T. w+ O: G  ?
7 i% U+ b" h; ians=0;
for (i=0;i<=5;i++)
  B/ S; l9 T' p6 P; S5 m    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
3 a3 z# q/ B; F* I/ m        {
. G5 |# m+ Y0 r5 ^! u; Z. ]            if (i+3*j+2*k>6)
                continue;
! T/ Z, Y  I) |9 `4 W- h1 A            if (i+j>5)
6 s/ u6 m1 c$ ]6 l                continue;
            tmp=dp[j][k];
            if (k>0)
' G: v9 u" Y  N) g0 |                tmp-=6;
0 O+ J) ], y! s: v! o" R3 s0 H" |            if (tmp>ans)
& t# r5 n, I3 z0 J+ ^1 {2 i4 {. x                ans=tmp;
        }
printf("%d\n", ans);
6 V! L- d; E; ~! S1 c/ Yans极为目标函数的最大值。

jerrybond6

( ]5 q/ J% B, [( _$ n7 \网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水