装箱问题算法实现讲解.doc

《装箱问题算法实现讲解.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、装箱问题算法实现讲解有一个箱子容量为V(正整数，0≤V≤20000），同时有n个物品（0≤n≤30),每个物品有一个体积（正整数）。要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。[样例]输入： 24    一个整数，表示箱子容量        6    一个整数，表示有n个物品        8    接下来n行，分别表示这n个物品的各自体积。        3       12        7        9        7输出：  0    一个整数，表示箱子剩余空间算法分析：本题是经典问题：0-1背包的特殊例子（加强了已知条件）。用整形数组volume存储各件物

2、品的体积，用布尔型函数h(i,k)表示前i个物品通过组合能否恰好装满容量k的空间，则考虑第i件物品，如果没有被选中，则问题转化为h(i-1,k);如果第i件物品被选中了，则问题转化为h(i-1,k-volume[i]),因此有如下的表达式：h(i,k)=h(i-1,k-volume[i])

3、

4、h(i-1,k);  k从V开始递减，判断h(n,k)是否为真，第一个符号要求的k即为剩余空间最小时消耗的体积。  如果此时直接编写程序，就要定义一个二维数组，空间复杂度时n*v,注意到了n,v的取值范围很大，所以用二维数组存储就会有问题。   我们注意到，h(i,k)的取值仅与h(i-1,0)～h(

5、i-1,k)有关，且如果h(i-1,k)=true,必然有h(i,k)=true,h(i,k)的值存在继承性，而程序结束时，我们也只关心h(n,k),因此，我们可以用一维数组h(k)来存储中间信息。为了避免重复计算，可以让k从大到小变化，为了避免出现负数，k的变化范围为v～volume[i].示例程序：#include#includeusingnamespacestd;intv,n;intvolume[31];//存储n件物品的体积inth[20001];//h[i]=1,表示n件物品通过某种组合，所构成的体积和正和等于i;            //

6、h[i]=0,表示n件物品无论如何组合，体积和都无法等于iintmain() {    freopen("in.txt","r",stdin);    freopen("out.txt","w",stdout);    intv,n,i,j,k;    while(cin>>v>>n)     {         for(i=1;i<=n;i++)          cin>>volume[i];         memset(h,0,sizeof(h));         h[0]=1;         for(i=1;i<=n;i++)          for(k=v

7、;k>=volume[i];k--)           h[k]=h[k]

8、

9、h[k-volume[i]];[Page]         j=v;         while(j>0&&h[j]==0)           j--;         cout<