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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
$ R7 V: U" K/ h0 H9 g  L& Q                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
and
                       x1>=0; x2>=0; x3>=0

! m  l% E  p8 ^+ u+ g当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

5 |) R2 u) {# ~: H0 g3 \' [& X用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

- G7 \2 a" ~) u9 X
2 I, h0 l0 V3 p4 u根据 s.t.可知 :
0<=x1<=5;
0<=x2<=2;
' W! Y, `" a# U0 U+ b( d1 M% H5 y0<=x3<=3;
# a$ h4 t$ f7 h  i% a$ D
: x, S3 T8 b6 g+ I2 X. J& z动态规划过程如下：

( A% n, x# C$ \# Oint dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));
. e' o+ D: w" S9 e3 H! O& d
8 u6 V) _3 ]: B! d; M2 e) G/ lfor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
            maxn=0;
' q& f" |, C( y, L# g  S# f" f6 y            if (i>0)
, L5 ]# ^( L: C- ^6 L) P1 G            {
) [5 o2 B0 i( j' _+ O: k+ X: x) b) }" D                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
0 ~+ ?' g* O" ~* q" E                    maxn=tmp;
* C& U; L$ ~0 A            }
            if (j>0)
1 O. p2 [3 d2 c/ S            {
! I% G% Y8 _5 _. _  h5 @, D; g! B, R                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
                    maxn=tmp;
& S( N. \$ i+ ~9 f; a0 d* I! W            }
7 ?: p6 U1 J- `7 D            if (k>0)
            {
( A/ U/ x. [! _5 S; g* O; K& v* P& |                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
7 P" A; e! p( d' p$ t: R                    maxn=tmp;
            }
            dp[j][k]=maxn;
        }
0 Y( P. _) ^- z/ h& ^8 m* E4 e
ans=0;
for (i=0;i<=5;i++)
& U% Z& U2 d- _) f! z; K    for (j=0;j<=2;j++)
2 z, X) H1 Y/ g! C5 q' S        for (k=0;k<=3;k++)
, `! `+ x# ~) b+ x        {
. Z8 K% w) V2 x4 ~/ r9 R            if (i+3*j+2*k>6)
1 `6 R1 t9 ?2 ~4 L, J                continue;
            if (i+j>5)
2 _( {. ^3 o# j, z( [( [, X                continue;
( _# P) ~' n' }: P) z- [            tmp=dp[j][k];
) D% x, `/ t9 H/ D3 h3 [: Z            if (k>0)
                tmp-=6;
            if (tmp>ans)
3 x  z; u! v, z( W                ans=tmp;
: s7 W# R" o5 `! B7 W        }
) ^- D; w! n& O+ u8 Sprintf("%d\n", ans);
4 }9 X" {, j% l6 O) C' _/ ~ans极为目标函数的最大值。
" q3 ]8 K3 x0 o8 @

jerrybond6

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

gaoshanliu水