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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
and
, v! w% \/ I2 V  v  |( Q                       x1>=0; x2>=0; x3>=0
. K2 E7 [$ u1 R2 Z: v5 }. d
当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
7 H" Y! L3 L/ P2 n7 I' o  _
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

根据 s.t.可知 :
0<=x1<=5;
' F6 _8 O3 |/ b# n; ^0<=x2<=2;
0<=x3<=3;
& X: b7 X7 ~* Q" I/ K0 _' o4 k$ x
动态规划过程如下：
3 t$ b/ p' ^( L8 H. L2 p
% T& d' U0 t. Iint dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));
! P, x. Q$ }) j: t. u
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
            maxn=0;
            if (i>0)
            {
4 o. F* I* t, W+ M& l. h4 p! |: r  s$ W                tmp=dp[i-1][j][k]+3;
, f$ M  ?# ?: [                if (tmp>maxn)
9 G6 P/ ]' U" d4 G                    maxn=tmp;
4 S; O1 `* {, j            }
            if (j>0)
            {
                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
6 k0 h$ V7 |# Y; u                    maxn=tmp;
            }
            if (k>0)
3 C+ |* ~! L$ j0 o/ t  S$ s            {
+ v, C5 s( o) I& `" G, u/ v# ~; Z) R4 s                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
3 i% R% ]' y) R+ i. p, S! K                    maxn=tmp;
            }
& B5 B7 T4 j) T$ W7 R& R9 H% \            dp[j][k]=maxn;
        }
2 `% i# P" S6 a% ~- [
' |# r: L: n, d: E$ k" F( Hans=0;
for (i=0;i<=5;i++)
  Y9 Y# |* p8 p) N& T: _    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
7 E" W: R' [/ v% H! e        {
            if (i+3*j+2*k>6)
                continue;
" M: p& j. l' }2 [            if (i+j>5)
                continue;
            tmp=dp[j][k];
            if (k>0)
. w! q, j1 N& _: N% I/ a                tmp-=6;
7 T9 S# g) Q( B1 x( R' y, v& k0 f            if (tmp>ans)
                ans=tmp;
9 y+ o. N  f5 z. l% Q% k5 M2 v        }
) F, _" G' b8 P. X" Hprintf("%d\n", ans);
ans极为目标函数的最大值。
! ]5 {3 \$ L( X1 y

jerrybond6

! q: }" @1 d, P- S* d7 Z) W
网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水