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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
9 X- P& ^/ `' Q. F1 R, Mand
                       x1>=0; x2>=0; x3>=0

当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
1 r* |  D: M4 ?* z0 x2 O$ L
6 y" q3 k* s2 w6 I- E, h用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

; K5 k1 r1 {* ], B$ J5 |- J% }! U
- E. d8 x4 s! E( }4 [- k4 C* ]2 S根据 s.t.可知 :
0<=x1<=5;
0<=x2<=2;
0<=x3<=3;
4 m6 D/ _2 P# q: b) H9 J
动态规划过程如下：
2 G+ ]3 H8 U0 B  T  L& J( r' {
int dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));

for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
9 y& |! ~  J, l, J9 ~        for (k=0;k<=3;k++)
/ W/ G5 A0 W, L$ d1 n4 y        {
8 i* O! i) @; W$ q  [            maxn=0;
            if (i>0)
' T! T9 ?: v$ E- S            {
  T- `4 h( \+ q2 Y. ~7 N0 ?! `! X                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
                    maxn=tmp;
            }
8 V( f8 [( |7 s            if (j>0)
            {
                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
                    maxn=tmp;
6 s* H6 s+ g% z( \' ^9 \            }
0 y4 {7 {3 }6 f6 G            if (k>0)
% `+ g8 S  z3 `! A& O            {
$ T/ P0 `+ w, K$ b( \) P                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
                    maxn=tmp;
            }
            dp[j][k]=maxn;
: P  V" ?! m0 ]4 q+ K1 P        }
, C1 o: o; D( @% q' [- G
6 ^( }/ B, h/ Z9 F& [+ W9 j/ Hans=0;
  P  `2 J7 Y* c: ?for (i=0;i<=5;i++)
1 k1 _$ a; W+ q" e9 C8 X    for (j=0;j<=2;j++)
) r8 m9 U. h* E& e        for (k=0;k<=3;k++)
        {
4 V/ C$ x  G( ?- x$ J            if (i+3*j+2*k>6)
: e% K; M+ f4 W1 s; T                continue;
            if (i+j>5)
                continue;
. u) `" X3 r. h$ |            tmp=dp[j][k];
            if (k>0)
9 r8 o8 E5 f& K5 F                tmp-=6;
            if (tmp>ans)
                ans=tmp;
        }
printf("%d\n", ans);
, |% p" T# P' m" y3 ~  Tans极为目标函数的最大值。
* E: p- J2 I8 i! X( j- X, }

jerrybond6

) z" w) l' D1 r$ h! d% w! @, j网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水