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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
: w6 a. w6 x, D                       x1 + 3 x2 + 2 x3  <= 6
% Z9 [2 P4 W7 M; S  k8 g- x% F6 p8 _: L                       x1 + x2 <= 5
; W6 \6 e7 ~$ a% T3 ]+ [and
9 ]+ ?# `8 C) |                       x1>=0; x2>=0; x3>=0
$ V& L' M9 d& g  T: B
# Q! q! V; w9 h3 I6 }0 C, B当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
( Z% [: h" W% E" X4 c" T
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

根据 s.t.可知 :
0<=x1<=5;
0<=x2<=2;
" k6 @9 t7 \; l: U- l" r! W1 H: b4 ~0<=x3<=3;
% {* n: V/ U" x) w5 x
动态规划过程如下：
- P0 Q2 ?4 o/ Y) t1 r; w
3 N( T; I. r2 }int dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));
: T7 E: O( L9 L6 M& ~
for (i=0;i<=5;i++)
+ I# v, [1 ?% y6 N5 ^* B3 z2 E, C    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
' @, l* I6 S( z2 G            maxn=0;
            if (i>0)
            {
                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
                    maxn=tmp;
            }
            if (j>0)
$ y5 }! I+ w! ~% W6 A2 J            {
                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
                    maxn=tmp;
8 E+ o  j5 ?3 r! Y  t8 B            }
            if (k>0)
; I6 F/ x. N$ }1 h" f" K) x( q2 B            {
7 ^% Y% d, T1 J. F, n% I8 {                tmp=dp[j][k-1]+6;
. m% l2 m" W+ l0 x% _3 n& `# Q                if (tmp>maxn)
7 F$ G$ N' N: L( [; C) a* I                    maxn=tmp;
            }
4 W2 a5 k8 a0 [& ~' [1 \7 a            dp[j][k]=maxn;
        }

% t( i: k7 M6 R" I! A" `" D/ ]ans=0;
for (i=0;i<=5;i++)
# O& u( X" ]' Y& ~    for (j=0;j<=2;j++)
' m$ F  c: t& Q        for (k=0;k<=3;k++)
        {
            if (i+3*j+2*k>6)
9 g8 y9 Z- F, d                continue;
5 U  J( _4 r6 z) {/ A8 g  L            if (i+j>5)
                continue;
% m, s1 w9 U2 A# A2 L            tmp=dp[j][k];
- b( Y  W3 x7 j. M4 _9 }( F            if (k>0)
# }7 n$ z5 T# l+ Y: T; d                tmp-=6;
; Y5 y# s) K# y. Z            if (tmp>ans)
                ans=tmp;
        }
/ y5 i$ z' h+ \$ Z% \5 `printf("%d\n", ans);
* t" e  h1 k$ H1 h) oans极为目标函数的最大值。
, i' [; S8 C6 ]& ^; X+ m7 O6 Q: `

jerrybond6

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

gaoshanliu水