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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
. m1 `" C. O+ _- U& b                       x1 + x2 <= 5
1 j* }9 i: L$ J, Y% Wand
/ v. Z! t/ G% S9 F! w, P                       x1>=0; x2>=0; x3>=0
" y) W& ^' V3 |+ [8 i2 @
, W) m# \* r* d1 ~5 d当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
3 \  p7 S0 {% Q" \- k, f
' V) U# M9 m1 H. y用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
( y) f) X# a3 T

jerrybond6

: l5 V) M8 M* }+ S+ h
: g# `) e+ {' R根据 s.t.可知 :
1 f* \: O' V) n  K' d0 C: v$ c0<=x1<=5;
0<=x2<=2;
0<=x3<=3;
( a: t( t9 e0 l# Z% c
' K; f$ A1 y' l3 i, j动态规划过程如下：
$ Y# D" S5 d! h
int dp[6][3][4], maxn, tmp, ans;

: Y% j8 N8 u; g# u. U9 [+ smemset(dp,0,sizoef(dp));

for (i=0;i<=5;i++)
" w" T. V. h% X5 G) y    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
; O& B/ ~2 X% _0 `1 C# |5 h( _        {
            maxn=0;
; T8 t* B" f& B$ F# D" L1 @. ]            if (i>0)
& ?7 G# X& \% z4 G* N            {
! S6 I0 e' E" Y  ?                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
' b9 F" M* B$ m7 G( x/ q, Q                    maxn=tmp;
1 F$ F3 [/ E# @1 n2 D5 Y            }
, G5 ^9 ?& D( _0 P7 X2 U            if (j>0)
  e/ s% Z! M) P) g+ T, s! y            {
                tmp=dp[j-1][k]+7;
* C: k/ s* L. ]# ?7 M2 W' `" V: d                if (tmp>maxn)
. q! G, e, O9 B! ?/ g. \                    maxn=tmp;
/ ^+ j+ k  L, N( M/ l1 e9 `            }
* V3 f# m& X7 g            if (k>0)
            {
                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
" {5 O$ ?; H" x$ u! W5 i                    maxn=tmp;
            }
            dp[j][k]=maxn;
: q' |2 j: z5 D, t1 H& j/ r; q* q        }

/ m: g0 G6 L: x3 {2 O; p& |) pans=0;
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
6 W5 a6 b( V+ _: f/ i7 ^        {
' X& X: ^2 K2 p# Q& z            if (i+3*j+2*k>6)
( k/ \; o# p2 ]) J% e! p) t/ a                continue;
+ ^' T4 w% l4 t, S            if (i+j>5)
                continue;
            tmp=dp[j][k];
* r! G% ]0 ]' v8 d            if (k>0)
                tmp-=6;
' v8 N8 Z; C7 M            if (tmp>ans)
                ans=tmp;
/ S& c+ \/ |! _( G) C  b        }
, C! e% W" D  k( Rprintf("%d\n", ans);
: V3 S0 l& d8 q- I+ Sans极为目标函数的最大值。
9 \# I& h, _2 t. U+ {  }

jerrybond6

- @: b$ X7 ^" m# m, [  M0 J
网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水