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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
% Q$ k4 ?. d4 Z! c4 k) y1 u                       x1 + 3 x2 + 2 x3  <= 6
8 u  l6 v3 ~) t4 i                       x1 + x2 <= 5
and
                       x1>=0; x2>=0; x3>=0

当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

7 u: [1 z% e! o+ T用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

gaoshanliu水

jerrybond6

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

jerrybond6

* Q" B  o# C$ Y% B根据 s.t.可知 :
0<=x1<=5;
0<=x2<=2;
) A. _# [, t  E0<=x3<=3;

/ T% [. a- ~/ F; L* g$ o) B) q- Q  m& r动态规划过程如下：
& {2 o1 `9 g$ D$ [
, E2 x. H$ x# r( l: @2 Lint dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));

) Z' G- F5 F1 u; Ifor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
/ S  i2 \7 _- M0 \, K) T; s        for (k=0;k<=3;k++)
        {
( ~2 |" h! v* y. c0 h            maxn=0;
" G  H( j9 e# ?& T& A8 Z- C            if (i>0)
            {
                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
( e  {# M, @2 n0 M                    maxn=tmp;
            }
            if (j>0)
            {
) Z7 _% q2 K( r. c8 \0 f' r                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
                    maxn=tmp;
' [# C/ q" P8 ?9 L* S9 Y2 s+ R            }
7 x; T7 H5 u' \# e6 q- K; Q            if (k>0)
! n$ P- t' p0 J0 x6 o            {
                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
/ `, b1 w7 l9 [0 V, O7 C4 R% w) M                    maxn=tmp;
4 Q/ [. l8 s! S  F1 F( @* P0 }            }
- X" l! v' Z- x. ^. w: V4 ^            dp[j][k]=maxn;
        }
' b' i* _' N8 Q+ M. {
7 s2 w0 w/ C( u/ F5 kans=0;
for (i=0;i<=5;i++)
% ^4 W5 P: c6 V6 ?7 V5 a    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
. z; S; c0 o% r" H, Z& }! H            if (i+3*j+2*k>6)
# G, f  G  P& P. p; m, i                continue;
- u% ]5 a8 Z" g, L4 f+ h            if (i+j>5)
5 g# d& e! p! B                continue;
6 d6 s1 a& W1 W' y2 g9 z, B! @            tmp=dp[j][k];
8 C0 z; B, F: J) b9 f            if (k>0)
                tmp-=6;
' [$ c% f' a7 p            if (tmp>ans)
5 w' X% n2 j+ o" y+ @- K2 J1 L                ans=tmp;
8 p2 @9 d$ H+ J6 Y* J        }
printf("%d\n", ans);
5 h$ a& F5 T) nans极为目标函数的最大值。
/ r9 m7 ?; L8 I