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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
and
3 H) a* s8 ]  I$ o% T& H) X3 r                       x1>=0; x2>=0; x3>=0
, F) b* ~9 b, ?$ F
! O" q  v) H6 e当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
, F+ g6 w  ]0 \0 E. P2 O, M- A
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

* F8 |7 h6 P7 V! L
+ a' `2 w  F# C: V根据 s.t.可知 :
0<=x1<=5;
0<=x2<=2;
+ u) D& f6 @4 y0 G* ?0<=x3<=3;

动态规划过程如下：

0 v& q- ~/ z& b" ?! Z/ Q( B* Oint dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));
3 `# q9 p2 G2 u1 G. k
for (i=0;i<=5;i++)
/ a) x- z$ X, I3 n) m+ J1 _: g    for (j=0;j<=2;j++)
9 F% c, v8 A. _* C" M' P        for (k=0;k<=3;k++)
9 N$ e8 E8 x& ]        {
            maxn=0;
( J4 _. o/ N5 H, d) ?4 r( X            if (i>0)
: x* ~+ ?- k& ~  G- t. n            {
% h! }7 F2 I' Y. i/ Q                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
                    maxn=tmp;
$ m( ^8 M; F& n* @! @* Y            }
            if (j>0)
  z- k. t* e/ i# ]* q9 _            {
                tmp=dp[j-1][k]+7;
5 `: Q) s8 z& q- t3 E. J1 _                if (tmp>maxn)
4 _1 i5 A* Y) ]6 a9 ^                    maxn=tmp;
            }
1 L* _% ]' N- K& T            if (k>0)
            {
                tmp=dp[j][k-1]+6;
  j$ D" s! C* y                if (tmp>maxn)
                    maxn=tmp;
            }
            dp[j][k]=maxn;
: m; _, B5 V! d4 `: X& ]        }

ans=0;
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
7 Q0 F! N' y  c. L, K4 L        for (k=0;k<=3;k++)
2 X- \6 }& A7 U# X/ l( k        {
            if (i+3*j+2*k>6)
                continue;
            if (i+j>5)
                continue;
            tmp=dp[j][k];
5 _' q/ ]% r4 T+ \5 k" q( W8 f; h            if (k>0)
* |/ k. A+ u7 x. u                tmp-=6;
            if (tmp>ans)
                ans=tmp;
        }
  t( d0 y. G% @2 I+ {2 `printf("%d\n", ans);
ans极为目标函数的最大值。
; d& U$ U6 \# v! }7 p( Y

jerrybond6

2 H; D; [6 X5 [+ k! u5 ~2 h/ I网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水