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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
* I9 G! u% ?4 c                       x1 + x2 <= 5
and
' H% Z; I/ ~+ {1 B1 w/ r                       x1>=0; x2>=0; x3>=0
  z; }# E- |1 v  M. T
8 A- O0 R  z, w当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
# ]+ K$ G) P* c: y6 B& m9 G; U. k5 G
3 Z% T1 H4 @9 G& h用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

根据 s.t.可知 :
0<=x1<=5;
0 Y7 N8 g8 J& h* h8 r7 O' L( D0<=x2<=2;
3 b. q  ~# S' U: @3 I. _0<=x3<=3;
( P* B) h) L. I, R
动态规划过程如下：
' ~& s) Z5 k9 v: B8 N
int dp[6][3][4], maxn, tmp, ans;

0 |8 V. r9 n. v+ Hmemset(dp,0,sizoef(dp));
- p9 R) s* a$ j
' A3 r. y: V% B; j7 K2 }" Gfor (i=0;i<=5;i++)
$ ^7 w7 V  W! X' ^+ h5 J+ B: w6 B% P    for (j=0;j<=2;j++)
4 ?$ i& Z9 D* ]8 V* R        for (k=0;k<=3;k++)
+ i, P0 K3 |* P$ t        {
            maxn=0;
2 L0 c, y& ?9 E$ |4 H. i            if (i>0)
* c* L- q/ P5 e+ l6 Z            {
                tmp=dp[i-1][j][k]+3;
8 Y8 j' m( C4 @0 F                if (tmp>maxn)
                    maxn=tmp;
$ i5 _" m- G, q9 F            }
5 k! K" }7 M( K2 N$ C  Q            if (j>0)
4 {7 \) {  c* b( j3 w            {
                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
$ m3 |, A8 O, C& J( K/ G" H$ d8 T& n                    maxn=tmp;
            }
            if (k>0)
            {
                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
                    maxn=tmp;
  ~% k1 J/ b% O: u( w- V1 j8 K            }
7 P! {0 o2 S( _4 s9 K5 i: @            dp[j][k]=maxn;
* u8 o0 G  l$ m& u. _1 L0 Y        }
* \% W- a: ]1 m' @! o
ans=0;
for (i=0;i<=5;i++)
+ f! y7 a% [0 T% Y    for (j=0;j<=2;j++)
& b# p' c9 d( ^" d( W2 H5 C        for (k=0;k<=3;k++)
- {% f! o1 m- H) R: M& L* }0 R        {
            if (i+3*j+2*k>6)
1 }1 x- h& |( U0 w, G' H' x                continue;
0 v1 b  R% A9 K$ s( W            if (i+j>5)
                continue;
            tmp=dp[j][k];
            if (k>0)
$ ^3 f: K5 Y) u                tmp-=6;
7 Q4 a/ G7 [2 M            if (tmp>ans)
  |# z3 W% Q5 c. [8 }                ans=tmp;
        }
printf("%d\n", ans);
9 f* Q6 ^0 {- }+ w. Aans极为目标函数的最大值。

jerrybond6

% z9 |* r$ D9 A/ \2 l
; Z6 c9 x2 J3 L5 K网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水