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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
! ~. t5 c1 C$ \; ^0 U* Qand
                       x1>=0; x2>=0; x3>=0
- R  [0 I$ ^$ M
当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
9 h+ t8 X& R# V" |+ L+ y

jerrybond6

: y! Q! C0 b+ l9 s
根据 s.t.可知 :
1 C9 c: y6 l& O5 a) C, p0<=x1<=5;
0<=x2<=2;
0<=x3<=3;

动态规划过程如下：
. |) J7 `) w5 U" _8 L, W7 d6 w
9 [5 }/ C5 m$ a9 ]5 O8 _int dp[6][3][4], maxn, tmp, ans;
& e3 ?3 m6 M/ A6 F. K5 s
, O; z* `' Y& U3 umemset(dp,0,sizoef(dp));

for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
            maxn=0;
1 |! y1 _4 m) _2 }. G            if (i>0)
4 n/ l( w' N- X  n4 O8 U            {
                tmp=dp[i-1][j][k]+3;
$ i1 p* A# ^" t                if (tmp>maxn)
' S. k5 G0 \; v7 L8 _8 v                    maxn=tmp;
2 o) a, ?' u& k9 g; V            }
5 f; `! _' Y4 V7 |# f            if (j>0)
            {
                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
/ n/ x% ?7 s2 p% O                    maxn=tmp;
- D& \: U* `+ Z1 G2 {! Q$ s# r            }
5 a" g; I$ z4 `$ M! {7 q8 R            if (k>0)
            {
  Y4 }1 z) E, z* `                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
                    maxn=tmp;
9 |( g+ e- {" Z4 ~1 K            }
            dp[j][k]=maxn;
" @' z" u# h; R" [. k        }
: Y* s6 u  c$ A+ u1 O, Q: n' W5 o
ans=0;
for (i=0;i<=5;i++)
% D8 }8 E" b) x, U8 E0 S    for (j=0;j<=2;j++)
6 G5 ^, p- ^/ q* m7 M/ i/ T        for (k=0;k<=3;k++)
# R. _5 ~: c+ t3 Z+ t' [/ s$ |; e        {
            if (i+3*j+2*k>6)
                continue;
' S. s+ M, D3 e; J4 T2 k! I            if (i+j>5)
! V8 C/ V* w+ V1 w3 J                continue;
3 f- c  U: p2 g+ a            tmp=dp[j][k];
1 y" S4 J- E3 F3 W5 F            if (k>0)
                tmp-=6;
: |6 P& r4 m! G$ D5 R8 b* _            if (tmp>ans)
                ans=tmp;
$ ~( f! b2 U6 D8 f! u        }
printf("%d\n", ans);
ans极为目标函数的最大值。

jerrybond6

$ C  K( r1 G! t9 z" B' e; X6 x
网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水