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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
                       x1 + x2 <= 5
and
5 n/ `8 C7 ]2 h$ Y- r                       x1>=0; x2>=0; x3>=0
1 V5 Y% z% M5 C% I0 r# }1 J
当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

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

gaoshanliu水

jerrybond6

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

jerrybond6

# H8 j8 ?# ~) O3 q  D9 C
. t* \, |) L" s$ c根据 s.t.可知 :
+ Q$ k4 X9 K- O; s2 B* j: N7 X$ j0<=x1<=5;
0<=x2<=2;
0<=x3<=3;
; C. D  q. o! b5 P. v
" W) B. H, S3 }动态规划过程如下：

. P9 b2 `0 V8 N$ a- O; `. ]int dp[6][3][4], maxn, tmp, ans;
$ n  K$ C6 g: X8 l4 ~3 j
: V; I( |% M( z. d4 H/ ]$ z" {2 umemset(dp,0,sizoef(dp));
* f3 g3 e$ o% ^& I3 R7 ]" h
0 B$ O( x" Q$ u: yfor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
+ R' H/ w) y0 b        {
            maxn=0;
            if (i>0)
            {
8 x5 k! C! g. g5 O2 |                tmp=dp[i-1][j][k]+3;
                if (tmp>maxn)
                    maxn=tmp;
            }
  j) ^# m* H  b4 C3 o8 `            if (j>0)
            {
                tmp=dp[j-1][k]+7;
1 U: g2 \# g& _* [" x; C3 n                if (tmp>maxn)
$ N0 o+ M: C6 m( q$ \                    maxn=tmp;
' a# I) W3 Z( ^; h$ w/ n2 P            }
            if (k>0)
* i2 v3 W8 w. z            {
6 }6 O1 S) K+ k' ]% }9 K+ V3 X                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
% l6 c# v  R/ d                    maxn=tmp;
            }
            dp[j][k]=maxn;
        }
% u$ z; y5 V) R6 l3 k; |/ \
, }/ [8 B0 g1 B+ l" m. i- vans=0;
for (i=0;i<=5;i++)
6 G0 D# p2 R: @0 g# `6 w. `    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
            if (i+3*j+2*k>6)
% i3 z7 S) V8 g" W5 U- c# z                continue;
9 V" o) e, G! }2 c            if (i+j>5)
                continue;
9 C% r- C- T8 }' a9 H            tmp=dp[j][k];
* O9 x+ d) T3 u4 `$ ~  |$ A! r6 X            if (k>0)
                tmp-=6;
# _- p$ V$ f# S' p            if (tmp>ans)
# {1 \, V4 Q( m! @9 @                ans=tmp;
        }
printf("%d\n", ans);
8 I4 p* C$ N0 Pans极为目标函数的最大值。