装箱问题最终解决算法.doc资源-CSDN文库

版权申诉

6 浏览量 2022-05-06 23:06:39 上传评论收藏 26KB DOC 举报

资源推荐

资源详情

资源评论

关于装箱问题应该大家都遇到过吧，不知道有多少人能写出他的解决算法，今天闲来无

事写了中个问题的实现算法，可能有做得不好的地方，高手不要笑话啊，旨在学习交流。

有一个箱子容量为 V(正整数，0≤V≤20000），同时有 n 个物品（0≤n≤30),每个物品

有一个体积（正整数）。要求从 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为

最小。

[样例]

输入： 24 一个整数，表示箱子容量

6 一个整数，表示有 n 个物品

8 接下来 n 行，分别表示这 n 个物品的各自体积。

3

12

7

9

7

输出： 0 一个整数，表示箱子剩余空间

算法分析：

本题是经典问题：0-1 背包的特殊例子（加强了已知条件）。用整形数组 volume 存储各件

物品的体积，用布尔型函数 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]) || h(i-1,k);

k 从 V 开始递减，判断 h(n,k)是否为真，第一个符号要求的 k 即为剩余空间最小时消耗的

体积。

如果此时直接编写程序，就要定义一个二维数组，空间复杂度时 n*v,注意到了 n,v 的取值

范围很大，所以用二维数组存储就会有问题。

我们注意到， h(i,k) 的取值仅与 h(i-1,0) ～ h(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<iostream>

#include<cstring>

using namespace std;

int v,n;

int volume[31];//存储 n 件物品的体积

int h[20001];//h[i]=1,表示 n 件物品通过某种组合，所构成的体积和正和等于 i;

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

内容反馈

版权申诉

老帽爬新坡

粉丝: 79
资源: 2万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip