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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
- F) B9 a/ \6 w                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
" z6 }7 l: b6 O0 Q' Iand
                       x1>=0; x2>=0; x3>=0
- D5 _$ S0 q& b( ~
' ?' M  Z. P5 W) \当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

4 x  y4 m! }$ G" U用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
/ R3 n. N3 B) Q% W

jerrybond6

2 H, J5 u! [- |7 C4 {' U, J根据 s.t.可知 :
9 {  H" w0 U/ w# @9 C# M7 T! b0<=x1<=5;
9 g. I$ u) s  M0 I, \% B( i  V- l0<=x2<=2;
0<=x3<=3;
/ V1 v) a! J# u. n" _
$ N0 {" Q/ \. q$ \  a4 M动态规划过程如下：
+ O/ a6 ~; u& d# U" F
int dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));
* J2 e3 s: e9 S9 J
, z9 G2 e1 D& @9 H/ Y/ k+ cfor (i=0;i<=5;i++)
2 }7 Q3 Z- ~( U2 \- h  d    for (j=0;j<=2;j++)
1 y" V5 H% r0 m! r! a        for (k=0;k<=3;k++)
. D/ W4 D1 `- X: ]        {
            maxn=0;
            if (i>0)
" K6 l$ x3 l+ v' Y1 n% O+ d' O+ t            {
                tmp=dp[i-1][j][k]+3;
2 Z# o& H: v/ I2 f, L; W- u) D                if (tmp>maxn)
                    maxn=tmp;
            }
            if (j>0)
: \% E! }1 h% }' I            {
7 m& l3 s) h0 N, ?; ]                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
                    maxn=tmp;
            }
            if (k>0)
            {
4 Z' d8 h+ O% _0 o8 v' S9 _                tmp=dp[j][k-1]+6;
$ R9 D$ h& \8 y, |# G2 t+ ^/ ^                if (tmp>maxn)
                    maxn=tmp;
            }
- \) y; U+ {% R/ y            dp[j][k]=maxn;
        }
8 x5 Y2 S% X5 |; q: Q- E7 [
% d/ T5 l; f" [2 T$ Kans=0;
# K  [1 G6 D, s# S7 t8 D" q" e1 mfor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
/ H7 H' Y+ u& ^5 u  v; O        for (k=0;k<=3;k++)
% x: E- j) H9 {% c: X: J5 B        {
* a3 |' v0 s, R8 q) S) }. M            if (i+3*j+2*k>6)
                continue;
  ^' i: k+ }/ \9 F& K- O" r& H            if (i+j>5)
( n" d+ |/ A: \8 C4 F% {                continue;
7 m8 r3 n" p' \$ q  l% P4 K3 n4 h            tmp=dp[j][k];
/ d8 ~  o. C: N4 c            if (k>0)
                tmp-=6;
            if (tmp>ans)
6 W& V) t1 \3 r5 q, D                ans=tmp;
        }
) S3 r6 d; r3 z9 s  a' @# m: yprintf("%d\n", ans);
ans极为目标函数的最大值。

jerrybond6

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

gaoshanliu水