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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
. m- a9 A" m8 ~. ~) w5 h0 z                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
2 k& s# W1 Z& Z, u; ?and
                       x1>=0; x2>=0; x3>=0
/ J( Z1 u6 }0 G
当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
9 H4 Y6 B7 Z" ]0 _
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

: v3 z, Y9 z- H
. l/ M6 n4 y5 _0 N0 y根据 s.t.可知 :
0<=x1<=5;
" C' ^7 c+ p, k+ I0<=x2<=2;
( M! T2 Z5 _, e* b$ K0<=x3<=3;
8 S  j( Z! z: z& r. b  D
动态规划过程如下：
' x& O% k% Z# w% U1 A/ F* {
int dp[6][3][4], maxn, tmp, ans;
: s& W# Z' q* @6 n% a) x! K
memset(dp,0,sizoef(dp));

5 x% H5 h2 x# F% F" Vfor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
& w- s- i% L- a; k, \/ W) a        for (k=0;k<=3;k++)
+ C9 ^$ U9 E: V; F! G        {
            maxn=0;
            if (i>0)
/ Q2 l$ r4 V2 d) J% z            {
- M' c& t$ t' g) }                tmp=dp[i-1][j][k]+3;
1 {  B+ Q" I7 m# r                if (tmp>maxn)
( t# L. Y; `8 T' J+ X+ z6 J                    maxn=tmp;
0 K2 j0 c6 s+ r* f            }
            if (j>0)
* g& ^- i$ k9 z) J            {
9 r# j7 Y- I7 i+ V$ u                tmp=dp[j-1][k]+7;
9 x9 \1 P) H; P4 B1 p* @5 o1 c! b                if (tmp>maxn)
2 n$ L5 M1 S4 [# E; x                    maxn=tmp;
. F% M- J8 m# f. x; x5 z1 [            }
$ b* v1 E. w* O4 M            if (k>0)
1 c$ N1 C! s7 U! j2 e            {
                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
9 l( U0 N% {; Q% r' t) S+ ^9 Y                    maxn=tmp;
            }
5 X, o. F- }+ h& L- [            dp[j][k]=maxn;
! M' ]& o6 J' N( E- k" Z7 C        }

0 @7 T1 \1 Y! t  P+ F( rans=0;
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
/ M9 \: _; y* g( w% K        {
. x) s" ?, W0 J4 ]: e$ K            if (i+3*j+2*k>6)
                continue;
, ~! c9 ?, \  p( f0 k# @1 q            if (i+j>5)
: @+ E  t7 _. z. ~$ w- Q! I                continue;
            tmp=dp[j][k];
6 C& \2 K7 g# F" F: r            if (k>0)
                tmp-=6;
            if (tmp>ans)
$ P1 {3 p& x5 l( x7 c+ r                ans=tmp;
        }
printf("%d\n", ans);
* l0 y- ~) @6 L  U* h: \* wans极为目标函数的最大值。

jerrybond6

; U/ t% `% [7 _/ w! A5 D
网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水