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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
% k1 B  B& b5 J& q) V                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
- F$ }  @. y) ?3 w% k, x# Uand
                       x1>=0; x2>=0; x3>=0
3 C# M& |! L) |' z7 ]
( H3 f* x3 O6 u+ Y当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

3 p! U" p5 Q$ ^2 G( e( j$ J# `
根据 s.t.可知 :
  J4 e2 x9 p6 f! Y0<=x1<=5;
0<=x2<=2;
0<=x3<=3;
- f; b, J  ~, }7 P: K7 r( J
动态规划过程如下：
5 s& P& t) e, W8 P
* ?3 I) F5 v" e! t  k7 yint dp[6][3][4], maxn, tmp, ans;
( w8 {7 t: q; a8 a
2 M. R* H, ?2 Y! x+ Dmemset(dp,0,sizoef(dp));
2 v; j8 V' s' T
for (i=0;i<=5;i++)
# z) l9 ?4 D: Y1 y, C    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
! i4 [) _" L  U, N        {
            maxn=0;
            if (i>0)
: ?- V' |7 J& E9 C; l6 F3 N, q            {
5 @; e( ^. S) T$ B3 M                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
                    maxn=tmp;
            }
            if (j>0)
6 s; w# i8 }; T0 B            {
3 c, W/ ]" l- b1 j. }& f5 \" g' N                tmp=dp[j-1][k]+7;
7 Q& G% Z9 m, c& P9 V% n                if (tmp>maxn)
+ [+ H6 O; u' @                    maxn=tmp;
3 L6 ^7 u( ]3 o, s            }
: V+ g3 w  X. Z1 I$ f- \5 \            if (k>0)
4 B7 e3 S6 m6 S3 R  j% [! a            {
                tmp=dp[j][k-1]+6;
+ C0 w, q: O3 I' B* y, Z! q9 y                if (tmp>maxn)
3 E4 N% u+ P' ~7 ?  _- L, S  _                    maxn=tmp;
            }
% n, Q3 |0 v0 ]9 M: X: `7 O            dp[j][k]=maxn;
9 y3 O4 \2 C+ U  \        }
( E1 }6 R: L6 J* T
  r; `3 C  R& j) N1 {$ Nans=0;
for (i=0;i<=5;i++)
+ v% K, M8 i3 a8 F    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
6 S; p4 `8 F: @; p; w        {
            if (i+3*j+2*k>6)
; R8 c2 ?) U! ^! [                continue;
            if (i+j>5)
1 D  P) c# w) Z; J7 j4 ~                continue;
8 m" G/ `2 [. ^% B8 s+ J6 ~            tmp=dp[j][k];
            if (k>0)
                tmp-=6;
            if (tmp>ans)
                ans=tmp;
9 u% b- b! p  N: ^( W8 b9 b        }
  N- i$ e- \& q! E0 Z& q# Rprintf("%d\n", ans);
6 }, c8 Y, q7 ]ans极为目标函数的最大值。

jerrybond6

& `# u, m' R, H+ O5 X
网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水