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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
$ i" _0 Y6 H  l5 E# u                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
4 y) _* h! U  T% g  B+ l) n& ~and
  q0 Q: z% _* K- \: v                       x1>=0; x2>=0; x3>=0
7 q; O. I. ?0 a0 P4 o8 N. O' g  F
/ S8 g7 Q9 K/ [0 _当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
4 y. c1 |7 F' y' M+ j. v8 g

jerrybond6

. K$ k' b. Q+ M) @" @
根据 s.t.可知 :
0<=x1<=5;
0<=x2<=2;
0<=x3<=3;

0 J' i' H! N! }动态规划过程如下：

int dp[6][3][4], maxn, tmp, ans;
* n* p# G' s. y5 q) m8 n7 K
memset(dp,0,sizoef(dp));
& g" r6 Y7 T: c* ^5 D; P5 I- n
/ Z- U) z( p% g; {1 y" T* lfor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
; ]1 G- a$ q, k) N        for (k=0;k<=3;k++)
; Z+ \/ N5 ?# `1 ~1 m+ V        {
            maxn=0;
            if (i>0)
            {
                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
; D! D1 S/ {& U                    maxn=tmp;
" ]( N( @; Y7 a" s7 H# ?            }
8 k8 T, [% M: i3 W& [- _            if (j>0)
& y8 q  Y" q. Z( S            {
( t* u( y$ e- p3 q  Z1 J. Q0 E8 f) z                tmp=dp[j-1][k]+7;
9 s; _5 M. k/ K                if (tmp>maxn)
                    maxn=tmp;
            }
2 g; \# |0 ?8 @$ J4 {" T, u            if (k>0)
9 ?' A# a( D" l) |# \            {
! ~( P- n, E! h                tmp=dp[j][k-1]+6;
* z4 e. `' y* z" d' s9 c/ ~- ~$ H                if (tmp>maxn)
                    maxn=tmp;
            }
8 v6 y' U9 H/ `& \% y+ E            dp[j][k]=maxn;
: E8 ]. ^1 F. a1 ?4 J! f$ k        }
* S& E# ^1 F+ A! ^% s3 C8 \
3 Z0 K# [4 z7 y. D  ~* _  Nans=0;
" {9 u8 b1 I9 Hfor (i=0;i<=5;i++)
# a( I- ?0 w: d+ M    for (j=0;j<=2;j++)
# W7 {7 A; k9 s9 C: N. q+ V3 Z. l! K0 |" r        for (k=0;k<=3;k++)
* `- h5 J/ J7 w) R. K1 M        {
            if (i+3*j+2*k>6)
; e, u. v3 N# I5 ?- l' G; G% J+ _                continue;
% R3 y# d0 z. Z& t9 n4 E8 }            if (i+j>5)
6 B7 ~) @9 ?7 n" G: ?2 |' d2 b+ g                continue;
            tmp=dp[j][k];
; g  y8 C# [5 ?$ r            if (k>0)
                tmp-=6;
            if (tmp>ans)
6 I& g" }+ N$ q' p$ @( U7 S, o                ans=tmp;
        }
' U: s: i) S) k( Y/ ]# x( ^: A7 t, cprintf("%d\n", ans);
1 A& z$ r# I2 aans极为目标函数的最大值。
9 b% O( H6 X0 w/ ]2 p

jerrybond6

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

gaoshanliu水