《33 装箱问题》由会员分享，可在线阅读，更多相关《33 装箱问题（10页珍藏版）》请在金锄头文库上搜索。
1、基于贪心法的装箱问题【问题】装箱问题问题描述：有一个箱子容量为 V(正整数，0V20000） ，同时有 n 个物品（0n30),每个物品有一个体积（正整数） 。要求从 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 【算法设计的思想】贪心法是求解关于独立系统组合优化问题的一种简单算法，求最小生成树的 Kruskal 算法就是一种贪心算法。贪心法的基本思路是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求
2、满足某些约束条件的可行解的范围。贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。例如平时购物找钱时，为使找回的零钱的硬币数最少，不考虑找零钱的所有各种发表方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪法。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为 1、5 和 11 单位
3、的硬币，而希望找回总额为 15 单位的硬币。按贪婪算法，应找 1个 11 单位面值的硬币和 4 个 1 单位面值的硬币，共找回 5 个硬币。但最优的解应是 3 个 5单位面值的硬币。若考察将 n 种物品的集合分划成 n 个或小于 n 个物品的所有子集，最优解就可以找到。但所有可能划分的总数太大。对适当大的 n，找出所有可能的划分要花费的时间是无法承受的。为此，对装箱问题采用非常简单的近似算法，即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常好的解。不失一般性，设 n 件物品的体积是按从大到小排好序的，即有 v0v1vn-1。如不满足上述要求，
4、只要先对这 n 件物品按它们的体积从大到小排序，然后按排序结果对物品重新编号即可。【算法的流程图】输入箱子的容积输入物品总数 N输入各物品体积预置已用箱子链为空预置已用箱子计数器box_count 为 0开始i=0;i#includeusing namespace std;int v,n;int volume31;/存储 n 件物品的体积 int h20001;/hi=1,表示 n 件物品通过某种组合，所构成的体积和正和等于 i;/hi=0,表示 n 件物品无论如何组合，体积和都无法等于 i int main()freopen(in.txt,r,stdin);freopen(out.txt,w
5、,stdout);int v,n,i,j,k;while(cinvn)for(i=1;ivolumei;memset(h,0,sizeof(h);h0=1;for(i=1;i=volumei;k-)hk=hk|hk-volumei; j=v;while(j0&hj=0)j-;coutusing namespace std;int f3120001;int main()freopen(pack.in,r,stdin);freopen(pack.out,w,stdout);int V,n,i,j;cinVn;int an+1;for(i=1;iai;for(i=1;iusing namespace
6、 std;int f20001;/fj表示前 i 个物品装入获得的最大体积int main()freopen(pack.in,r,stdin);freopen(pack.out,w,stdout);int V,n,i,j;cinVn;int an+1;for(i=1;iai;for(i=1;i=1;j-)if(jusing namespace std;ifstream fin(pack.in);ofstream fout(pack.out);int f20001;int main()int v,n,a31,i,j,d;finvn;for(i=1;iai; for(i=1;i0;j-)/j 为剩
7、余空间if(fj=1&j+ai0&fd!=1)d-;fout#includeusing namespace std;int v,n;int volume31;/存储 n 件物品的体积 int h20001;/hi=1,表示 n 件物品通过某种组合，所构成的体积和正和等于 i;/hi=0,表示 n 件物品无论如何组合，体积和都无法等于 i int main()freopen(in.txt,r,stdin);freopen(out.txt,w,stdout);int v,n,i,j,k;while(cinvn) for(i=1;ivolumei;memset(h,0,sizeof(h);h0=1;for(i=1;i=volumei;k-)hk=hk|hk-volumei;j=v;while(j0&hj=0)j-;coutv-jendl; return 0;
