??nk?1
k?1m
?③?0
?采用m次nk 张照片的扫描方法更好
由（1-11）可以直观的看出，扫描操作时间为m的一元一次函数，且随m的增加，时间也增加
150100t5000246810m1214161820
?T1?m?minT1?min(m) （1-12）
综上可得，要取得最短时间，必须控制扫描的次数最少，由于已确定使用A4幅面扫描，其宽度为D1，每张照片宽度为di（i=1,2,3…,10）,照片所占宽度为（di+0.5）
??(dr?110r?0.5)D180??3 21?P?4?少于4次不可能把所有照片扫面完，即m?4
9
5.1.3 建立模型及求解
运用动态规划方法建立模型，把照片扫描过程划分为多阶段处理，分别建立了在扫描照片最大张数下的数学表达式，然后运用LINGO软件求解。
a.通过枚举思想建立模型
通过对照片扫描过程的分析，我们将扫描情况划分为5种情况求出电子化过程的总时间T，并且图像处理时间都是50s, S13 =120s: (1) P=1：
第一次：4+1+(2+1+S13+1+2) 第二次： (2+1+S13+1+2) …
第十次： (2+1+S13+1+2)+1
Ta=5+10（6+S13）+1+50=1316s
(2) P=2:
第一次:4+1+(4+1+S13+1+2) 第二次： (4+1+S13+1+2) …
第五次： (4+1+S13+1+2)+1
Tb=5+5(8+S13)+1+50=696s
(3)P=3:
第一次：4+1+（6+1+S13+1+2） 第二次： (6+1+S13+1+2) 第三次： (4+1+S13+1+2) 第四次： (4+1+S13+1+2)+1
Tc=5+2(10+S13)+2(8+S13)+1+50=572s
(4)P=4:
第一次：4+1+(8+1+S13+1+2)
10
第二次： (4+1+S13+1+2) 第三次： (4+1+S13+1+2) 第四次： (4+1+S13+1+2)+1
Td=5+(12+S13)+3(8+S13)+1+50=572s
得到用时最少的数学表达式为
n??T?4n?nS16?6?2?nXmax??(Xmax?Xi)??T1
i?1??
此题最优化的方法为：
当P?5时不存在组合情况，因此只能在P?4情况下考虑，通过结果可知，
Tc=Td=572s,因此采用组合(3,3,2,2 )和(4,2,2,2)两种情况下的照片组合能够使用时最少，最快完成电子化过程。
在组合（4,2,2,2）下4张照片一起的只有（3,4,5,6）和（3,4,5,7），剩下的6
2张照片排列组合有C6=15种，因此共有30种情况。
b.动态规划（0-1规划）模型 (1)模型的建立
对于 张照片，长度相同，且已知第张照片的宽度为正数 片的宽度和价值相等），最大容纳下的扫描幅面宽度为正数的一个子集，使得子集中照片的总宽度不超过扫描幅面宽度
，价值为正数（照
，现要求找出这 张照片且总价值尽量大。（由上
述模型中可知，照片只能正放，故不考虑照片长度的影响）。
根据问题描述，可以将其转化为如下的约束条件和目标函数：
于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量。
0-1宽度问题可以看作是寻找一个序列，对任一个变量的判断是决定等于1还是等
11
于0，在判断时，会有两种情况：
a) 扫描幅面宽度容量不足以放入照片，则等于0，价值不增加； b) 扫描幅面宽度容量可以放入照片，则等于1，价值增加；
这两种情况下总价值的最大者应该是对判断后的价值。令表示在前张照片中能够放入到宽度为
的扫描幅面宽度的总价值，则可以得到如下的动态规划函数：
式（3）说明：把前面张照片放入扫描幅面宽度为0的扫描幅面和把0张照片放入扫描幅面宽度为 的扫描幅面中，得到的价值均为0.
式（4）第一个式子说明：如果第 张照片的宽度大于扫面幅面的宽度，则放入第 张照片得到的最大价值和放入第不能放入扫描幅面中；
式（4）第二个式子说明：如果第张照片的宽度小于扫描幅面的宽度，则会有两种情况：
1. 如果把第张照片能放入扫面幅面宽度为 的扫描幅面中，则扫面幅面的价值
等于前
张照片放入宽度为 的扫描幅面中价值与第张照片价值之和。
张照片得到的最大价值是相同的，即第 张照片
2. 如果第张照片不能放入扫描幅面宽度为 的扫描幅面中，则扫面幅面价值就
等于把前
张照片放入扫面幅面宽度为 的扫描幅面中的价值。显然，取二
者中价值较大者作为把张照片放入扫面幅面为 的扫描幅面中的最优解。 (2)模型的求解 第一步，只放入一张照片，确定在各种情况下扫描幅面能得到的最大价值；第二步，只两张照片，确定在各种情况下扫描幅面能够得到的最大价值；依次类推，到了第就得到所需要的最优解。
最后，便是在扫描幅面宽度为中，放入 张照片取得的最大价值。为了确定装入背包的具体物品，从价值向前寻找。依此类推，直到确定第一个物品是否被装入背包为
12
步
止。由此，得到如下的函数：
根据动态规划函数，用一个二维数组存放中间变量，表示把前张照片能放入扫面幅面宽度为 的扫描幅面中取得的最大价值(程序见附录1)。
5.2 问题二模型建立及求解 5.2.1 问题分析
该问题是在第一问的基础上增加照片的数量以及将照片划分为3种长度各20、20、10张相同尺寸的照片，并且要求使用分辨率为300dpi,对于该问的解答我们通过0-1规划问题并且进一步分析知道，
5.2.1.1 理论模型
由问题一中的(1-1)式知：
T=T1+T2
由题目知道，设分辨率为DPI，已确定为DPI=300dpi，并且照片长度lr均为26cm,最短的照片宽度为mindr?5cm，因此满足
lr?min?dr??1?max?Lk??k?1,2,3? （2-1）
即：26+5+1=32>29.7>27.94>25.7
由（1-2）、（1-3）的约束条件可知：
不存在组合lr? dr，即
图四
13