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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
6 I: E; z& O/ A6 ?" Hand
  e8 Q, X% ~0 E1 ]                       x1>=0; x2>=0; x3>=0
  G9 A- [: E9 t7 O) \
2 o7 A: F: T* l8 h# W  Y3 t. N* h当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

+ |) d* q( T6 l9 E8 _用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
, I3 Z, o+ t& b2 d8 E" ?# y

jerrybond6

  C' ]& M) i7 @5 o* r- O
根据 s.t.可知 :
7 {- q2 k# N8 u5 O# S% m2 ~; M% w+ K+ z, K0<=x1<=5;
0<=x2<=2;
! g5 f4 t" I9 t7 L0<=x3<=3;

动态规划过程如下：

& Y; s4 o4 v, z0 O- Wint dp[6][3][4], maxn, tmp, ans;
: `, U- W. G3 k5 f6 K( P% ?3 ^
. e$ _: ?" i! n& V/ Xmemset(dp,0,sizoef(dp));
2 F* Z, N( c6 ?9 j. _4 }
; h1 K) w% r) u; A% Ufor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
  K, P' w4 ~. x2 y8 E& j  Y( ^: l        for (k=0;k<=3;k++)
        {
7 ?5 w! t5 `. V1 K            maxn=0;
            if (i>0)
- R( Y9 s9 E: \/ Z            {
5 K" T% J' y- j2 l9 D; S                tmp=dp[i-1][j][k]+3;
3 q9 E' O* M8 I) @0 U2 W                if (tmp>maxn)
1 L: [7 Y7 z" j, F! g- ^, M                    maxn=tmp;
  G0 q; b) f2 {9 t/ g: A, S            }
            if (j>0)
/ E" }. B' K  E            {
* U( ], Y6 ?4 W# t4 n$ }  r/ _4 |                tmp=dp[j-1][k]+7;
1 W3 ^4 d* {5 n: l* [- _                if (tmp>maxn)
0 e; A( E, k0 ]                    maxn=tmp;
. x- _2 R/ C  x$ i( E            }
            if (k>0)
            {
( M% J1 i* q- c1 ~; Y6 N                tmp=dp[j][k-1]+6;
( Z5 Z, O  |- A( s  ~                if (tmp>maxn)
                    maxn=tmp;
9 ]* o9 y. Y4 h+ H% Q9 z            }
7 [) B0 y( y, G% R1 J            dp[j][k]=maxn;
( s$ K! M$ I+ g  c1 j4 H        }
& ?& A/ |  u6 Q5 n/ |
" f; Q4 M/ V' @/ K7 E3 uans=0;
+ s' O, P5 D7 T! u$ t  Qfor (i=0;i<=5;i++)
1 X3 l$ e( M; V# m0 _    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
* ~% H6 B# O" @) |  x* e: M+ n# r        {
            if (i+3*j+2*k>6)
9 C5 {) D3 I# e5 m, }& I: o1 m                continue;
            if (i+j>5)
                continue;
            tmp=dp[j][k];
! w; M; m  I4 u, f4 J0 J1 L: P% ?$ O9 ~            if (k>0)
6 v  T  b6 b7 d; e7 i$ f                tmp-=6;
            if (tmp>ans)
                ans=tmp;
        }
2 J2 k. [$ o2 X6 [7 ]( Z# j# Y1 Zprintf("%d\n", ans);
+ @! X# n8 \; L$ x- n3 Ians极为目标函数的最大值。
! D& I! A  l( F; P, B0 G" o

jerrybond6

  g% n$ z* q6 ^( L3 C5 k, x9 P
网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水