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

zhaobener

Max                Z=3 x1 + 7 x2 + 6 f(x3)subject to  
                       x1 + 3 x2 + 2 x3  <= 6
" k! ]  G9 c8 s                       x1 + x2 <= 5
and
                       x1>=0; x2>=0; x3>=0

( A, V  a5 @1 F1 a当 x3=0 时 f(x3)=0;  当x3>0时， f(x3)= -1 + x3

用动态规划来解 谢谢（lingo之类的我知道如何求解 主要想知道计算过程）
% h0 q$ a2 G+ }# m9 e& {8 e

jerrybond6

* g) n% g8 ?/ e5 `: h/ L2 s
根据 s.t.可知 :
0<=x1<=5;
0<=x2<=2;
0<=x3<=3;
2 ?1 K, {# H8 C- @/ E
3 |: g$ x/ k5 [4 |动态规划过程如下：
# x9 p( E. ~# f
% M" a4 E, M  Uint dp[6][3][4], maxn, tmp, ans;
8 s- b4 v1 q% Y7 p: [
memset(dp,0,sizoef(dp));

9 c% v9 o  f9 S; Tfor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
( a7 {& Z! E  [$ ?, Z3 w            maxn=0;
            if (i>0)
            {
                tmp=dp[i-1][j][k]+3;
) L3 N# O* r- ?4 _& Z. ~                if (tmp>maxn)
                    maxn=tmp;
            }
, ]3 Q& ]+ m1 B; m3 c, T0 V, U            if (j>0)
            {
                tmp=dp[j-1][k]+7;
                if (tmp>maxn)
                    maxn=tmp;
2 p0 ?$ l2 s6 ~            }
            if (k>0)
            {
. L5 F2 C8 R" d8 @& F7 @                tmp=dp[j][k-1]+6;
                if (tmp>maxn)
! ?6 v5 d( @( H+ L' J4 M* @/ v+ O7 L                    maxn=tmp;
            }
& c' r) |5 t# v2 `            dp[j][k]=maxn;
        }

" g7 @& }4 m9 Z8 k' O8 G9 Pans=0;
4 p; h4 c+ d; f0 o) ufor (i=0;i<=5;i++)
    for (j=0;j<=2;j++)
        for (k=0;k<=3;k++)
        {
            if (i+3*j+2*k>6)
. Y6 t! Q# P7 O- {                continue;
& p9 B4 {  K5 q0 q2 F! z9 g            if (i+j>5)
2 K+ s  m) S  M                continue;
            tmp=dp[j][k];
            if (k>0)
                tmp-=6;
            if (tmp>ans)
& G4 B8 M' A$ M: P                ans=tmp;
/ d+ ~4 C; o/ p3 v1 H! @  D6 L        }
# U' h( O3 Z* ^7 Q8 D' V3 U2 O; oprintf("%d\n", ans);
& Q$ p& E, M$ w# ians极为目标函数的最大值。

jerrybond6

3 y* m7 M; z; K+ X7 ?5 g, L( X
网页有点问题哈  数组有的地方显示的是2维 应该是3维    你自己琢磨琢磨哈  要是不明白想知道对不对 自己拿程序照着写一个 跑一下 和lingo对比一下就知道了

gaoshanliu水