【题10】装箱问题

【题10】装箱问题有一个箱子容量为v（正整数，0v20000），同时有n个物品（0n30），每个物品有一个体积（正整数）。要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入：箱子的容量v 物品数n 接下来n行，分别表示这n个物品的体积输出： 箱子剩余空间输入输出样例输入：24 6 8 312797输出： 0 题解1. 使用回溯法计算箱子的最小剩余空间容量为v的箱子究竟应该装入哪些物品可使得剩余空间最小。显然在n个物品的体积和小于等于v的情况下，剩余空间为v-n个物品的体积和。但在n个物品的体积和大于v的情况下，没有一种可以直接找到问题解的数学方法。无奈之下，只能采用搜索的办法。设a和s为箱子的体积序列。其中ai为箱子i的体积，si为前i个箱子的体积和（1in）；best为目前所有的装箱方案中最小的剩余空间。初始时best=v；确定搜索的几个关键因素：状态（k，v）：其中k为待装入箱子的物品序号，v为箱子目前的剩余空间。目标vbest：若箱子的剩余空间为目前为止最小，则best调整为v（bestv）；边界条件（v-（sn-sk-1）best：即便剩下的物品全部装入箱子(未装物品的体积和为sn-sk-1)，其剩余空间仍不小于best，则放弃当前方案，回溯；搜索范围：在未装入全部物品的前提下（kn），搜索两种可能情况：1. 若剩余空间装得下物品k（vak），则物品k装入箱子，递归计算子状态（k+1，v-ak）；2. 物品k不装入箱子，递归计算子状态（k+1，v）；我们用递归过程search(k，v)描述这一搜索过程：procedure search(k，v:integer)； 从状态(k，v)出发，递归计算最小剩余空间begin if v=best 若箱子即便装下全部物品，其剩余空间仍不小于best，则回溯then exit；if k=ak 若剩余空间装得下物品k，则物品k装入箱子，递归计算子状态then search(k+1，v-ak)；search(k+1，v)； 物品k不装入箱子，递归计算子状态 end；thenend；search主程序如下：读箱子体积v；读物品个数n；s0 0； 物品装入前初始化for i1 to n do 输入和计算箱子的体积序列begin 读第i个箱子的体积ai； sisi-1+ai；end；forbestv； 初始时，最小剩余空间为箱子体积if sn=v then bestv-sn 若所有物品能全部装入箱子，则剩余空间为问题解 else search(1，v)； 否则从物品1出发，递归计算最小剩余空间输出最小剩余空间best；2. 使用动态程序设计方法计算箱子的最小剩余空间 如果按照物品序号依次考虑装箱顺序的话，则问题具有明显的阶段特征。问题是当前阶段的剩余空间最小，并不意味下一阶段的剩余空间也一定最小，即该问题并不具备最优子结构的特征。但如果将装箱的体积作为状态的话，则阶段间的状态转移关系顺其自然，可使得最优化问题变为判定性问题。设状态转移方程 fi，j在前i个物品中选择若干个物品（必须包括物品i）装箱，其体积正好为j的标志。显然fi，j=fi-1，j-boxi，即物品i装入箱子后的体积正好为j的前提是fi-1，j-boxi=true。初始时，f0，0=true（1in，boxijv）。由fi，j=fi-1，j-boxi可以看出，当前阶段的状态转移方程仅与上一阶段的状态转移方程攸关。因此设f0为i-1阶段的状态转移方程，f1为i阶段的状态转移方程，这样可以将二维数组简化成一维数组。我们按照下述方法计算状态转移方程f1：fillchar(f0, sizeof(f0),0)； 装箱前，状态转移方程初始化 f00true； for i1 to n do 阶段i:按照物品数递增的顺序考虑装箱情况 begin f1f0； i阶段的状态转移方程初始化 for jboxi to v do 状态j：枚举所有可能的装箱体积 if f0j-boxi then f1jtrue；若物品i装入箱子后的体积正好为j,则物品i装入箱子 f0f1； 记下当前装箱情况 end；for经过上述运算，最优化问题转化为判定性问题。再借用动态程序设计的思想，计算装箱的最大体积 k=。显然最小剩余空间为v-k:for iv downto 0 do 按照递减顺序枚举所有可能的体积 if f1i then begin 若