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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
$ a& C* Y( t9 ]% i1 \: f3 l% m                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
and
                       x1>=0; x2>=0; x3>=0

* I. r/ s/ `% ]4 g9 {: x当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）

gaoshanliu水

jerrybond6

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

jerrybond6

根据 s.t.可知 :
- `* a$ ~. y1 T$ C5 L) \: Q* ^0<=x1<=5;
* e  `+ s" Z& N7 @0<=x2<=2;
0<=x3<=3;

动态规划过程如下：

* D* _+ T' t4 J8 _# }int dp[6][3][4], maxn, tmp, ans;
1 O5 ~) F% g- x4 T: r7 s
+ i$ r5 A* A, f, Mmemset(dp,0,sizoef(dp));
8 ?, U$ H  B; a' ]. N, E
for (i=0;i<=5;i++)
& h  t' I1 E5 C5 M1 m+ N    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
3 b  u: T7 c/ G        {
1 L$ a1 \6 b# C: t1 D( _            maxn=0;
' a2 x, A2 m+ v6 y! G            if (i>0)
' O% T3 K* S7 u* U& {4 E- ^            {
                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
                    maxn=tmp;
# a0 L# [4 B1 ~' i3 X4 \: Q* F            }
            if (j>0)
            {
( y* ]# L1 F1 T" [2 B                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
                    maxn=tmp;
            }
5 e4 q& L: z2 @7 _            if (k>0)
$ L+ r+ {4 I1 z* H) _" M            {
- p0 L6 ]0 D$ S3 Q) k                tmp=dp[j][k-1]+6;
6 Q$ u- X' O' m# {& o7 t                if (tmp>maxn)
                    maxn=tmp;
            }
7 l/ K* \6 x% f. C            dp[j][k]=maxn;
        }
+ i7 @6 }: Y- B
! Y' |3 H) @9 o& oans=0;
for (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
, C% [+ E7 M: s# Q1 M            if (i+3*j+2*k>6)
2 j- v& `- [4 s3 \7 }                continue;
  l# B3 R% w3 j) J$ K            if (i+j>5)
# w6 O0 t! M; ?: t; U1 Y; K                continue;
            tmp=dp[j][k];
7 l# M* f6 U& j            if (k>0)
# j. |+ h+ H0 R8 R, \; z                tmp-=6;
1 {4 X8 z1 a6 \9 D' [: d+ H            if (tmp>ans)
! B/ o  _7 J  O" a- i/ b6 @                ans=tmp;
        }
printf("%d\n", ans);
ans极为目标函数的最大值。
$ U' Z* o  y% {0 s4 n! z! _* d