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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
6 V& @/ R! C6 [. O) p                       x1 + 3 x2 + 2 x3  <= 6
" h1 m% U+ }; @# ?$ {, q                       x1 + x2 <= 5
and
+ D( ~! f5 L" m' t/ p, h) E                       x1>=0; x2>=0; x3>=0

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

用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
0 h9 @, j5 l# F

jerrybond6

* p3 F3 Y- b. u0 O0 A  g9 h; P
% V$ a* C. H. y" K/ ?9 _根据 s.t.可知 :
0<=x1<=5;
8 {; h" }( z" Q5 F+ {0<=x2<=2;
0<=x3<=3;

动态规划过程如下：
5 x" P6 }" p  S
int dp[6][3][4], maxn, tmp, ans;

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

8 M+ Z/ t8 w- _for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
( B4 _7 O( a  R$ \: d        for (k=0;k<=3;k++)
        {
            maxn=0;
( w, [- x9 Q* @0 j$ R            if (i>0)
            {
$ b5 T9 `6 c. l; g1 y                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
                    maxn=tmp;
+ P1 O" j: n+ Q  C            }
, D' ~% u3 G/ i            if (j>0)
            {
                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
( @$ W, M7 r9 E+ v7 ?7 F                    maxn=tmp;
6 e6 r) q4 `4 p9 n9 r            }
            if (k>0)
            {
                tmp=dp[j][k-1]+6;
& ^5 H  D( L8 n- X# I6 c; Y# n/ |1 E                if (tmp>maxn)
+ ~( y  e- R/ I% ^                    maxn=tmp;
            }
            dp[j][k]=maxn;
        }
) d+ b4 g" g6 P2 P- X
ans=0;
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
9 x& P3 F; v7 \# _) X        {
            if (i+3*j+2*k>6)
                continue;
            if (i+j>5)
                continue;
% p7 T3 [7 t% L# [            tmp=dp[j][k];
            if (k>0)
                tmp-=6;
1 r, |. a9 I( A- Y$ K$ b            if (tmp>ans)
  }: i6 M6 r& w+ ]' @: _                ans=tmp;
        }
  S. X4 X" d4 b" m* Y9 oprintf("%d\n", ans);
0 j& h9 a" |& `1 z; D' c! oans极为目标函数的最大值。

jerrybond6

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

gaoshanliu水