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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
8 i' t& n/ n9 p! q7 V  z" ?* I9 ?                       x1 + 3 x2 + 2 x3  <= 6
+ d# |+ Y( ~" Q. I  I                       x1 + x2 <= 5
' f( d3 r4 C5 land
2 A5 G$ [: D- _0 t% q5 c2 C                       x1>=0; x2>=0; x3>=0
: `1 {5 I3 s8 T! R0 A- F' k% Y4 l
当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
- q! U+ j+ \3 n; W5 j
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
0 F0 P! M) q& K% S0 a

jerrybond6

: N3 m+ G0 L" W' H
( `7 X2 o* q; v7 R/ t5 r根据 s.t.可知 :
0<=x1<=5;
  W7 M) r+ |1 h  j% Y0<=x2<=2;
" n; V7 f* ]+ R2 q0<=x3<=3;

动态规划过程如下：
0 k  q& ?) _' w6 c& Z8 n
int dp[6][3][4], maxn, tmp, ans;
' }/ {) K5 R/ X7 P) }3 @+ R
memset(dp,0,sizoef(dp));
: x8 N  Q0 L  v9 V+ }
for (i=0;i<=5;i++)
6 Y2 ~2 L! g+ M9 H    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
            maxn=0;
            if (i>0)
, y: X1 Q" E% V% K; D  E3 V            {
                tmp=dp[i-1][j][k]+3;
1 z9 d) y+ ?8 ^                if (tmp>maxn)
2 A! F6 T9 x7 G  Y- L                    maxn=tmp;
9 E8 U' {! m3 g5 r            }
) d% O# B9 [4 P. ~7 X            if (j>0)
/ n# w$ t, ?2 w6 a2 q& e. V! A            {
                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
                    maxn=tmp;
7 L' s1 ]. {$ b) E; Y3 c2 F5 ^            }
            if (k>0)
            {
                tmp=dp[j][k-1]+6;
+ @# O7 D0 G( v& |7 [                if (tmp>maxn)
) V7 M/ q2 t6 v, F& A# A0 c8 s                    maxn=tmp;
0 c" t6 V  K& t            }
0 X4 [8 |% _% p/ R! E! U/ z" d            dp[j][k]=maxn;
( h0 x' t# F# O1 \4 P& _) N        }
" }+ \/ i" L7 K- f8 I% {1 t
3 @5 F, X* G3 V% J4 |. V% Oans=0;
$ y1 d0 c4 X" q, f- x: d+ R/ dfor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
9 \8 M. [/ ~. @8 P        {
; \6 |( h+ r( ^            if (i+3*j+2*k>6)
                continue;
4 n1 r" F) l  ^9 b5 e' ^: H5 K            if (i+j>5)
8 n" D' \6 `1 m' V! x$ ]                continue;
/ C7 E7 ^( {" D            tmp=dp[j][k];
            if (k>0)
7 A, r' Q" Z: O( Q; X                tmp-=6;
/ b5 [' u6 o& v$ j# r1 S, j            if (tmp>ans)
8 W1 N. a7 Y: f: T, x! z* j1 L                ans=tmp;
/ Z* S6 _. C7 b6 `8 t" A: [9 c        }
- \+ E; q1 ^* I2 c; }  G1 S) I, g; Rprintf("%d\n", ans);
; t, r; w) g/ S: }4 qans极为目标函数的最大值。

jerrybond6

# B% _1 O- G6 S2 N  b" j, J9 l$ b; w网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水