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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
" B* a0 `9 l! d* c+ h- Fand
                       x1>=0; x2>=0; x3>=0
; M  N. R. ?5 B. x" r4 {, z
2 a- v$ A+ _$ D+ I$ |当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

$ P1 c0 Y9 h4 ]! x8 I8 L用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

  ~3 T/ k- |6 ]1 l5 S
+ ?  \# k0 p: b1 |6 U根据 s.t.可知 :
7 ~' @, e% i& t9 `/ W( ?' D& t5 m0<=x1<=5;
0<=x2<=2;
1 t  I; M# m4 S/ I' W8 f0<=x3<=3;

动态规划过程如下：

4 i, [2 O: R. f5 G' iint dp[6][3][4], maxn, tmp, ans;
4 _" P) [" W' j+ F8 D  p  `
memset(dp,0,sizoef(dp));
0 [& i) b% G6 B1 @( x
; J/ O- u. m: P; _# j! ?7 o& ]' P9 tfor (i=0;i<=5;i++)
) e4 a0 n" Q/ o2 w" ?6 s- ~    for (j=0;j<=2;j++)
1 y' O5 u* n/ v& T& u7 p) Z        for (k=0;k<=3;k++)
        {
4 C* j( a) s$ _3 C            maxn=0;
1 u; u" q! w+ ^/ E% T: O            if (i>0)
            {
) Q4 P3 V8 I; f6 S8 l7 D0 Q& s                tmp=dp[i-1][j][k]+3;
6 D6 _- N8 L5 ?/ h/ a                if (tmp>maxn)
5 d1 I% H, c9 S& m6 S7 g6 w                    maxn=tmp;
            }
            if (j>0)
' x& _/ Y0 ~* ?5 D            {
% P1 S1 d0 k' {+ f% N9 ?) |                tmp=dp[j-1][k]+7;
( ^' @5 J4 C: D/ d- M5 A. U                if (tmp>maxn)
                    maxn=tmp;
            }
            if (k>0)
            {
' c& x1 \  M; O                tmp=dp[j][k-1]+6;
/ n( \7 }9 \$ I/ Y9 y                if (tmp>maxn)
: p  o8 F0 c  C+ X- w2 s* z                    maxn=tmp;
. x8 \. r+ |! |3 K. v1 U            }
            dp[j][k]=maxn;
        }
+ }8 P+ G5 d: ~5 H& |) J* B
ans=0;
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
' l; Q9 `/ B) x        for (k=0;k<=3;k++)
        {
            if (i+3*j+2*k>6)
& D; U  D1 {- j                continue;
            if (i+j>5)
                continue;
  X1 n1 R* E; \( [            tmp=dp[j][k];
6 Y$ G" W+ w! x- t2 q            if (k>0)
+ ]! c7 n' p) F, Y9 Y: ]9 s! Q                tmp-=6;
            if (tmp>ans)
                ans=tmp;
        }
printf("%d\n", ans);
ans极为目标函数的最大值。
9 j4 f: X! r. z. m$ B

jerrybond6

+ M0 E, H# ~$ G2 B5 L
8 l" }8 Z( q5 J3 o* Z网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水