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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
) o8 x% J6 n+ A* P* [                       x1 + x2 <= 5
and
) M) K4 B/ \2 z2 c* W/ v+ o                       x1>=0; x2>=0; x3>=0

' w5 Y$ f4 h( V8 U7 F% h/ e/ A& H当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
  X, v+ X6 x0 f4 m  k+ S6 W
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

根据 s.t.可知 :
: @8 K1 M3 Y( {6 @" J. \1 j0<=x1<=5;
0<=x2<=2;
0<=x3<=3;
1 r4 \. U  m" @1 j( j5 A8 |
- |4 Z2 |$ @- ?" ~% x9 m; e. G- L动态规划过程如下：
# v# ~6 u) O& J% E$ x! d" K) B
" c( h+ {* R5 m8 D5 R. ]% Mint dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));
( Z+ n6 i" I, W  c6 p
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
9 b( ~! `/ |- ^6 P. _9 b# X6 p. a        for (k=0;k<=3;k++)
        {
            maxn=0;
            if (i>0)
            {
                tmp=dp[i-1][j][k]+3;
( a# J' n$ M% n) ^  Q                if (tmp>maxn)
                    maxn=tmp;
            }
            if (j>0)
            {
6 Y0 a3 L0 w; e* H                tmp=dp[j-1][k]+7;
: O: F# J' @0 _0 [9 Z4 n4 j0 X                if (tmp>maxn)
                    maxn=tmp;
            }
9 b! |; V- ]* ]2 \  G; @            if (k>0)
            {
                tmp=dp[j][k-1]+6;
3 t1 x; [4 V& z; K/ [                if (tmp>maxn)
                    maxn=tmp;
; s& v7 F+ G; @# w0 I/ s            }
            dp[j][k]=maxn;
' p/ u' l$ w4 P, F$ d. s$ u  }        }

ans=0;
- m( _2 [- N3 s* {: afor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
1 R! x: u: \" Q7 l7 t$ V        {
6 M1 j0 ]0 P! M. B% f& N; C            if (i+3*j+2*k>6)
8 f# X) g3 T- O( j( R0 p                continue;
7 s1 ~8 w3 z8 ]7 \+ h$ ]2 g0 D            if (i+j>5)
0 _1 K/ i0 f7 I; M                continue;
            tmp=dp[j][k];
& J, ?& P) H: w9 u+ C5 ^            if (k>0)
                tmp-=6;
+ {0 Z. Z  f! I2 v8 M" y            if (tmp>ans)
8 |% P% R1 {* n0 f0 U: F1 b                ans=tmp;
6 j5 K" ?1 C3 R1 b        }
8 a$ ~/ J1 o& y  T; V, Lprintf("%d\n", ans);
* Z* L* ]$ j# _; H) _ans极为目标函数的最大值。
7 D+ v7 R8 ]$ ?

jerrybond6

& Z% o1 W% g' ]6 w3 d; i
6 R* c& m4 v  A& U9 r网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水