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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
- I& Q( i' c& w+ Z; }% f( T                       x1 + 3 x2 + 2 x3  <= 6
( G& d$ [# K, C                       x1 + x2 <= 5
and
; Z- l4 |, l* U: S% @. E- Z                       x1>=0; x2>=0; x3>=0

  Q) g$ e6 c7 d+ Y6 W当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
3 L6 M7 b4 i- t. c) F5 B
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

, ^" s% j! ~+ T2 g- h) d
根据 s.t.可知 :
' j- W( V2 [8 W( K' t* h0<=x1<=5;
0<=x2<=2;
0<=x3<=3;
: g$ ?8 f6 z! _  U) [
5 y$ y3 [, P3 }: u! B$ L5 Z/ L动态规划过程如下：
$ ~& i, q' X, E- S
/ p1 w! I& n; J: w/ [2 |* h: Iint dp[6][3][4], maxn, tmp, ans;
" Y5 n1 G* Y4 S" T
memset(dp,0,sizoef(dp));
3 r; L/ ^) S! ~+ T. f
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
            maxn=0;
            if (i>0)
) W+ }" }) H. @+ f5 m6 r  X            {
                tmp=dp[i-1][j][k]+3;
7 k: j6 ?0 y# w0 U3 Y                if (tmp>maxn)
                    maxn=tmp;
            }
. F( L% o8 e$ x4 P$ d            if (j>0)
- w( i; c* \6 G4 m% g0 x            {
8 }7 F+ B% v$ V$ m1 x$ a                tmp=dp[j-1][k]+7;
6 J# D: U7 M$ D# f                if (tmp>maxn)
3 O* ^6 F" o* q* P# f% G                    maxn=tmp;
% `8 i( Q& W; u" j( U# b            }
            if (k>0)
            {
4 [; _' G% @) V4 \0 w, N! y                tmp=dp[j][k-1]+6;
* [+ N+ w5 [: R, P8 g/ L6 w- @; g                if (tmp>maxn)
5 I* D+ x: Z- _- f  C                    maxn=tmp;
            }
            dp[j][k]=maxn;
6 A% S6 s4 _" M6 A, f; z        }
7 X& P% l: F6 q- F- c( S+ i7 k* G4 |
4 y  `* a/ T9 Tans=0;
9 X1 p* k( w5 k$ o4 ?for (i=0;i<=5;i++)
( P3 l8 x+ \" C4 E" T7 {1 @    for (j=0;j<=2;j++)
' {2 W3 a3 I0 H7 W+ c( i        for (k=0;k<=3;k++)
        {
3 V6 W7 ^$ i0 z$ U0 t, q            if (i+3*j+2*k>6)
                continue;
$ \8 I$ S1 d+ i) U! R( ]            if (i+j>5)
                continue;
            tmp=dp[j][k];
8 {' Z9 n/ h: W+ }- U            if (k>0)
2 ~1 w5 U2 m  _; b                tmp-=6;
            if (tmp>ans)
                ans=tmp;
        }
& f4 D/ V2 D) Qprintf("%d\n", ans);
ans极为目标函数的最大值。
7 Z1 l1 B/ C7 _: M

jerrybond6

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

gaoshanliu水