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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
. r6 x& i/ _  p0 r3 z                       x1 + x2 <= 5
and
% x/ z5 X0 g6 f                       x1>=0; x2>=0; x3>=0
2 Q* c; V; {# [8 H+ S5 Q4 `& G
% U# c: G+ i9 f7 f0 R- q1 q+ g当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
% L- {- C$ p. s: \; N
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
, ~0 f) r; l) v3 r

jerrybond6

根据 s.t.可知 :
, x* f4 q! m/ k9 |" p0<=x1<=5;
0<=x2<=2;
3 l. [; h6 K* B0<=x3<=3;
& H- m( o& G/ R6 U" V( L
' _' l' \3 I/ n% R0 _动态规划过程如下：
5 z/ F" Y4 H4 h* k: O# g
/ B4 }' h+ S+ N) kint dp[6][3][4], maxn, tmp, ans;

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

  e7 q3 \0 V/ Bfor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
/ ^8 ?6 H$ p8 s! r4 C) ?, \        for (k=0;k<=3;k++)
7 i7 C  \" D4 N! K        {
            maxn=0;
: X/ m* G, o4 T1 P! X7 |            if (i>0)
. ~& b0 Q. y, ]6 S( }8 L            {
# R3 H3 g* o; t' Q                tmp=dp[i-1][j][k]+3;
$ @8 _2 D2 {4 W: K8 `                if (tmp>maxn)
3 |1 B, {; f) d: ~8 T0 {7 s* D                    maxn=tmp;
" W! _  Z/ C9 n3 A- P            }
# p3 E& [" @' N8 W/ G- H            if (j>0)
$ T1 w. d$ h7 X+ m+ P7 E            {
                tmp=dp[j-1][k]+7;
. o/ r6 R: v9 e* o# b5 k+ o                if (tmp>maxn)
                    maxn=tmp;
            }
5 R+ R3 T( `( A. D2 Y. l1 `            if (k>0)
  B2 r* \6 @, C2 E. S            {
1 ^* R3 b- j& W. F( M' Y' B3 z                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
) C/ E' C9 @) E6 H                    maxn=tmp;
% u  }- x$ `! O            }
1 Z5 Q5 G, `' E4 Z            dp[j][k]=maxn;
/ S( H% P  E$ u        }

" K2 ?' G) t# L$ R7 k& lans=0;
. _0 ^: k: _$ P' O2 E* s3 Ofor (i=0;i<=5;i++)
! b/ Z& Y0 a2 [9 Z( q# u    for (j=0;j<=2;j++)
8 e% g5 C7 Q1 F' }$ r        for (k=0;k<=3;k++)
1 F9 U, ]% b) T+ b9 E4 ]' B7 h        {
            if (i+3*j+2*k>6)
                continue;
            if (i+j>5)
                continue;
4 n+ T1 z4 w) x$ h5 c0 L            tmp=dp[j][k];
) T. N2 N+ B* |5 T. u4 i            if (k>0)
3 K3 ~- d) K# ]% V$ d$ V8 k                tmp-=6;
            if (tmp>ans)
                ans=tmp;
        }
printf("%d\n", ans);
; f% T5 D8 |, D' U1 sans极为目标函数的最大值。
- U+ o+ i6 G# h- R; i- Y

jerrybond6

0 j7 P+ _; [8 W/ e3 `3 R
网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水