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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
! d, G/ ~1 v, W' C0 u8 n0 ^, g" Q1 _                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
, A3 l- U5 E7 }% I2 i# D! Rand
                       x1>=0; x2>=0; x3>=0

# B6 N9 g) z0 l" k当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3
1 C) |6 O& `: Y+ Q
用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
$ e5 a6 b! L0 L: c& c- K

jerrybond6

根据 s.t.可知 :
" S! s  a: H5 N3 i3 M! J" e, Z+ B: K$ ^0<=x1<=5;
0<=x2<=2;
4 r$ G5 B3 ?; a0<=x3<=3;

# h% X  Q; @/ w" [6 Y5 k. v' k" g$ e动态规划过程如下：
$ o5 A; V# e0 F6 n; ?
int dp[6][3][4], maxn, tmp, ans;

memset(dp,0,sizoef(dp));
1 L5 l$ `& O# v
6 D' A$ X4 X' U& d$ Z( Z+ {/ Nfor (i=0;i<=5;i++)
! _) q: M. s, Z    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
# d6 d9 X$ q; k7 ^7 u9 S: W$ q! E            maxn=0;
            if (i>0)
            {
                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
. H2 {  M0 K: Q* {                    maxn=tmp;
            }
; t( x5 v8 x& l) P8 w( n            if (j>0)
  X6 I+ w9 r1 ]+ k- N; }$ \8 j0 [            {
" O' c- v* o/ P  X' b4 \( ~                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
                    maxn=tmp;
8 E9 W1 N7 u! H- ?: Y3 e            }
1 C; ~9 F/ [! l% B! B' I' V6 r6 T            if (k>0)
            {
                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
/ k' I1 L) r: |' q& i                    maxn=tmp;
* B5 f) o9 ^9 ^( l            }
* ^! x; }( w9 S- i) @6 A            dp[j][k]=maxn;
        }

ans=0;
- R7 a! s( X7 f( a! ofor (i=0;i<=5;i++)
5 _) V- A* ?* _- i    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
; K) z+ I) t3 Z  t5 T            if (i+3*j+2*k>6)
* a: Q6 h6 }' }) s; R: l  x                continue;
            if (i+j>5)
- }4 T. y# J: Q' A8 d* y- r1 ?, l                continue;
7 x# h, u5 a  j; S, y6 K7 H. W            tmp=dp[j][k];
0 Z+ N, A$ x( Q8 Z4 V            if (k>0)
' C+ O( x) p6 e7 K- N                tmp-=6;
$ E( O. x# a$ m5 j# A* O5 b2 @) b            if (tmp>ans)
) S' C' u* T0 g: I                ans=tmp;
4 ^1 E. ]3 k4 o) A0 ~5 N        }
" y0 d- s7 H: m5 W- I8 ~1 F9 sprintf("%d\n", ans);
ans极为目标函数的最大值。
& Z8 n: G; O. C: I: W9 R7 I; \3 B, U2 V

jerrybond6

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

gaoshanliu水