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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
. J( F' U7 W" g9 m                       x1 + x2 <= 5
7 {% a; o' B: eand
                       x1>=0; x2>=0; x3>=0

当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
% E2 D/ V% ~* D0 W( `2 d3 u- H- R# F
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
/ O5 T7 |- P) B& p. H. w

jerrybond6

8 c1 o% [0 i" V* a1 K3 X( \+ u: I+ l
* J7 |: h- h# U& d& }根据 s.t.可知 :
0<=x1<=5;
0<=x2<=2;
7 s( F9 b1 ^( L. r0<=x3<=3;
0 ^( ^  p( a7 K$ ^
( Q) Y% ^2 d& }& e% M' ]! {动态规划过程如下：

* V( b5 \0 e* r' w/ C/ ~int dp[6][3][4], maxn, tmp, ans;
# z3 g  Z/ A+ Q3 D
memset(dp,0,sizoef(dp));
+ `: y4 Y/ C' p
! L( m) D% _+ \! z, p0 S/ jfor (i=0;i<=5;i++)
& c9 p/ R, V' n. g0 J    for (j=0;j<=2;j++)
) F% w/ D/ Q" S* O        for (k=0;k<=3;k++)
        {
            maxn=0;
2 N7 Z3 p( r0 z0 T: V! Q            if (i>0)
            {
" P1 [/ d. o1 {0 P/ Y" C9 E9 L( P                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
0 E/ H' b4 v- }+ P9 [                    maxn=tmp;
            }
: e6 |& Z: l% w; Z            if (j>0)
            {
3 w$ i& j7 B) u/ y3 H& P                tmp=dp[j-1][k]+7;
! x" i7 ~1 y8 ]  T  r8 `- |                if (tmp>maxn)
1 s+ T8 k) p+ b( h6 @9 Y                    maxn=tmp;
; @: B; Y5 a( \( ?1 w            }
            if (k>0)
            {
# l. @% |2 E# W3 z4 r                tmp=dp[j][k-1]+6;
+ e6 ?, l; Y# o( t: Z, K4 S                if (tmp>maxn)
                    maxn=tmp;
- `( T" N) A. n1 G- X3 p" W            }
6 c; a/ b2 X' q: L$ w# L            dp[j][k]=maxn;
        }

ans=0;
1 n% u9 M3 B9 [6 qfor (i=0;i<=5;i++)
! Y) B' [- i; o. K3 C9 C    for (j=0;j<=2;j++)
; l! e- X. l2 E4 F5 S& G        for (k=0;k<=3;k++)
% K8 D/ ~9 K( h6 D2 v: C        {
            if (i+3*j+2*k>6)
2 f# h! k0 S7 b( B1 k% E                continue;
            if (i+j>5)
                continue;
, V3 t1 b$ J* y" I+ o            tmp=dp[j][k];
            if (k>0)
                tmp-=6;
            if (tmp>ans)
0 e# y! [8 B- B7 C* H1 B) i' \: V                ans=tmp;
1 Y& I9 c, W$ q: ?0 W        }
7 ~  _: N5 h6 k( Y  v+ [7 \printf("%d\n", ans);
/ W0 L" e3 ^% aans极为目标函数的最大值。

jerrybond6

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

gaoshanliu水