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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
/ u) P  j- G$ k, d* o                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
and
                       x1>=0; x2>=0; x3>=0

当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
* q; J% N! J" W- Y3 A1 Y6 ?& s
! C% e* t. T& Y9 E7 b/ _用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

jerrybond6

根据 s.t.可知 :
0<=x1<=5;
  ~7 }: I" u7 p) N7 S# w$ e0<=x2<=2;
* A' M: P) t8 K, V" M1 R0<=x3<=3;

动态规划过程如下：

( s( `( B  B3 g0 v# ~int dp[6][3][4], maxn, tmp, ans;

* q/ I5 {; k* P$ t+ imemset(dp,0,sizoef(dp));
/ P" b& f7 V5 `, q0 o- F
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
1 h2 S8 L6 s4 {# `/ _) u1 N# h        {
/ E- i: {2 a1 N; Q" G- @5 B( @2 a1 J            maxn=0;
/ s! B9 n+ k. o  R( F6 Z            if (i>0)
            {
) m: ?3 y# u3 p3 w3 Y                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
/ W2 y! i# d- M6 Q1 R. }                    maxn=tmp;
            }
            if (j>0)
            {
                tmp=dp[j-1][k]+7;
' N- R* {# ?2 }2 R9 q  T! E1 b                if (tmp>maxn)
                    maxn=tmp;
+ I+ n/ R- B# t# I# {            }
            if (k>0)
5 s4 {6 v* H1 |8 F! s& y) g            {
* ~+ k- A6 M: f9 \, n0 p8 o* M( u                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
                    maxn=tmp;
5 X& f  M9 T( t( U9 v            }
  s1 m1 Y# B5 a0 R4 n) `; u8 z, ^+ h            dp[j][k]=maxn;
* p: |5 L' y% ^; b        }

ans=0;
  A# E" Z# X. s; Y( jfor (i=0;i<=5;i++)
* l# }* K' v2 ^- x    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
: c4 h2 w1 W0 {" j. m. K1 G: H        {
            if (i+3*j+2*k>6)
2 M9 n, Y5 z7 {+ m                continue;
) l5 l8 t  `! U) Y# z' l            if (i+j>5)
                continue;
            tmp=dp[j][k];
& }5 P$ y1 r. g% U3 h1 |" a            if (k>0)
                tmp-=6;
            if (tmp>ans)
                ans=tmp;
0 p! b* e. k, x4 B7 s! n! u        }
printf("%d\n", ans);
ans极为目标函数的最大值。
8 O; {3 W8 m# a

jerrybond6

* ~  d, o* C  D- k5 h* C9 A8 L/ m/ X
网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水