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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
0 `" i3 E  M0 G3 K  D7 p                       x1 + 3 x2 + 2 x3  <= 6
  w! F  x4 A! q7 @3 v5 u3 Z) P                       x1 + x2 <= 5
and
                       x1>=0; x2>=0; x3>=0

当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
0 i& ]+ y+ p, A8 S2 o8 U" O; u# g
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

8 n$ Q2 J/ M! q+ V- j1 R根据 s.t.可知 :
0<=x1<=5;
! o; l/ Q0 X" H, x7 x0<=x2<=2;
0<=x3<=3;
' d+ d; v4 w6 X. Z
. R* g6 R* A, @" L$ r; u  |动态规划过程如下：

int dp[6][3][4], maxn, tmp, ans;
( Z) _- k, s! d% e; ~' O5 E) s
memset(dp,0,sizoef(dp));
9 O$ I4 s- M, \+ c
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
: R( W) D, D$ ~/ ?: S9 _/ L        {
4 |+ ~! j( c0 r0 m9 K: N& j, T5 e            maxn=0;
! K1 Y3 L0 n8 L1 ^, e            if (i>0)
            {
9 |% g( h5 ~( q: I                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
                    maxn=tmp;
            }
! g* Y1 A5 F, i( y+ _9 A) W$ M            if (j>0)
; x" R, j: u& Q% x) t: y/ h            {
* J$ b8 [! x- G- J                tmp=dp[j-1][k]+7;
- Z- H) N7 o2 t( j1 @4 R                if (tmp>maxn)
7 C  t* ?; `8 [& ~0 ^* K. ]                    maxn=tmp;
            }
            if (k>0)
5 E7 a( y! l' `: z3 H' Y' U            {
                tmp=dp[j][k-1]+6;
: M, s9 \1 |) e+ h' X                if (tmp>maxn)
9 F( U8 _' [1 \" B% l2 X                    maxn=tmp;
            }
            dp[j][k]=maxn;
, G1 v% M# V1 I1 [        }

ans=0;
) i) G  d# G! C" p$ c9 vfor (i=0;i<=5;i++)
" u9 o8 U! M) S: S0 t    for (j=0;j<=2;j++)
4 G( \( m$ u) }0 p4 `        for (k=0;k<=3;k++)
9 d3 P. {# X& T$ ]4 {0 H        {
            if (i+3*j+2*k>6)
+ O3 n$ U# U+ Q& G4 I                continue;
            if (i+j>5)
                continue;
8 Q6 q) a2 F% f  v3 M            tmp=dp[j][k];
8 ?6 L, P; `! U' i8 Y4 n7 ?            if (k>0)
) S. \& u* n, q; W9 @; h                tmp-=6;
# P# N9 l# Q- k; `2 k            if (tmp>ans)
                ans=tmp;
3 S3 |+ w* L' ?$ }6 C1 \        }
printf("%d\n", ans);
9 Y  Z. K2 r0 g8 j1 M+ e) |ans极为目标函数的最大值。

jerrybond6

2 y* `, T% r5 k% M" O# ]5 m网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水