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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
% S! W8 y1 A# g3 |/ N: n) r, @! `                       x1 + x2 <= 5
and
                       x1>=0; x2>=0; x3>=0

当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
  J9 H$ w, r0 X4 a# x3 o
; g7 v0 y* O' X4 O用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
2 X! C/ j! u: B/ [

jerrybond6

根据 s.t.可知 :
: q8 Z& z& }7 E) y5 [0<=x1<=5;
( v# u4 B. S# ^( i1 c' D0<=x2<=2;
0<=x3<=3;
5 J3 i! a( t$ c& B- n# u. W# e/ P: K
; t  V+ U3 w: N' k$ X$ |3 P动态规划过程如下：

int dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));
6 h1 }5 B% R7 _8 W7 q
3 V9 f4 F& _3 ofor (i=0;i<=5;i++)
1 M3 v8 ~, y  j/ L    for (j=0;j<=2;j++)
+ E% k# M6 i6 c5 z# u        for (k=0;k<=3;k++)
, ?6 Q7 O! x; F1 E! ]  Y" F        {
            maxn=0;
            if (i>0)
            {
                tmp=dp[i-1][j][k]+3;
4 ~! X7 l2 Z# l% n                if (tmp>maxn)
# G; n+ Y( Z5 L                    maxn=tmp;
" E6 K: d  ^1 N0 A) |" z; Z  ]            }
4 c! Z# ], J7 H/ q7 a" {            if (j>0)
            {
/ c0 B7 |1 C9 Z7 j                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
7 v1 u# F8 v- e$ j                    maxn=tmp;
$ o; f8 p0 I* n% d            }
, P' g4 ]5 y5 U' y; r            if (k>0)
) D1 j1 T( v& x# q* ]3 Y            {
  a5 H) X1 k$ h/ f2 U& x2 [( W! t: G                tmp=dp[j][k-1]+6;
5 Y. C- [, p! T                if (tmp>maxn)
3 p3 I9 {8 _& x; t4 h$ z6 X+ k  n9 L9 T                    maxn=tmp;
5 r/ b* H* H# M/ g5 r0 U* I2 {            }
* L' o4 H( k3 M3 t            dp[j][k]=maxn;
& M0 J4 d4 Z4 ?! U        }
6 b, o. {% x4 u5 X1 m
ans=0;
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
# d: ^8 k' q' w1 g, K        {
% l3 M& {7 W4 L' p. R% l7 F1 r6 r6 R            if (i+3*j+2*k>6)
7 j3 u! w* \, ~4 Y, `                continue;
            if (i+j>5)
3 E5 c' S0 r0 n                continue;
8 d% Y) B% y0 ?! G            tmp=dp[j][k];
- ^/ w3 S! y6 M            if (k>0)
                tmp-=6;
            if (tmp>ans)
2 k# b2 n" V  {/ ^# \, o                ans=tmp;
5 _/ X3 Q6 G7 |$ q5 M# w/ f! Q" d        }
printf("%d\n", ans);
ans极为目标函数的最大值。

jerrybond6

$ m5 y3 p5 T( D, E网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水