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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
and
* Q( b2 i! w8 c; a4 b5 [                       x1>=0; x2>=0; x3>=0
1 t" F/ k1 @3 x
当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
& h. [. z4 a' _* \1 t
3 x! o! t! {/ F$ w/ p8 |" L6 b用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
  v" ]+ X2 N# |$ f, {& |8 e

jerrybond6

根据 s.t.可知 :
0<=x1<=5;
0 g% W% M2 T& ^8 j1 e0<=x2<=2;
0<=x3<=3;
% s) ^8 P8 l, D) i- m
动态规划过程如下：

9 Z. z9 H- x) a* D# L9 i6 n4 Kint dp[6][3][4], maxn, tmp, ans;

8 u& C* R1 t8 u8 C' _" |/ \3 d& Gmemset(dp,0,sizoef(dp));
6 Q2 |$ P$ A- A1 j9 }
* `" Y" X) j' ~( xfor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
5 y& P0 b3 n; G4 A        {
/ L3 d# c9 h: S% m& E& r            maxn=0;
            if (i>0)
            {
                tmp=dp[i-1][j][k]+3;
0 N  V- R! t3 v; k, M  D8 T                if (tmp>maxn)
: ~  V* i4 F  l3 A  d: h$ z4 ^                    maxn=tmp;
            }
            if (j>0)
  x$ n2 p: I6 b7 b2 k( V7 u6 ^            {
                tmp=dp[j-1][k]+7;
$ a2 w, y8 [3 x- H9 N                if (tmp>maxn)
                    maxn=tmp;
            }
' J% [2 E$ o" p) N. L            if (k>0)
0 m; }5 O! s0 z            {
# n4 S4 e3 d( q) [8 S- ?  L  S                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
                    maxn=tmp;
            }
            dp[j][k]=maxn;
% J& d  T0 n/ U* W) A. z, q        }

. N& F2 Z; n' @0 U" `ans=0;
# ^9 ~% F# F7 K/ Gfor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
8 y7 W- I* Q$ H& f! F1 J        for (k=0;k<=3;k++)
* s% v; r3 q0 o- X- Z! ~. l        {
            if (i+3*j+2*k>6)
3 `" X. D4 K3 ?                continue;
            if (i+j>5)
                continue;
- L/ T* T/ v) h            tmp=dp[j][k];
            if (k>0)
+ ^! q( g8 A9 _* T                tmp-=6;
6 s) ~' a" C7 {4 W$ Q* m  H            if (tmp>ans)
                ans=tmp;
        }
printf("%d\n", ans);
ans极为目标函数的最大值。
3 m3 v7 L1 U: a& ^/ C

jerrybond6

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

gaoshanliu水