贪心算法之装箱问题

2021/5/10 22:25:50

本文主要是介绍贪心算法之装箱问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

问题描述

装箱问题可简述如下:设有编号为 0、1、…、n - 1 的 n 种物品,体积分别为
v0、v1、…、vn-1。将这 n 种物品装到容量都为 V 的若干箱子里。 约定这 n 种物品的体积均不超过 V ,即对于 0≤ i<n,有 0<vi ≤ v。不同的装箱方案所需要的箱子数
目可能不同。装箱问题要求使装尽这 n 种物品的箱子数要少。

贪心求解

使用一种贪心策略:每次都想将当前体积最大的物品装入箱中,在这块类似于这个问题 ->>> 贪心算法之多机调度问题
其实在生活中这也是很常见的一种做法,在没有充足时间去考虑如何最优解决这类问题时直觉(第六感 狗头保命)告诉我们可以这么去试试。
更直接的一个例子,力扣上有这么一道题:
在柠檬水摊上,每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。 每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。 注意,一开始你手头没有任何零钱。

注:上面黑体部分内容引自力扣LeetCode860 柠檬水找零
很明显,当客户给我们$20进行找零时,自然而然地就给ta找了一张$10加上一张$5,为什么这么做?面对$20,我们有两种方案可以使用:

  • 找三张$5给顾客
  • 找一张$10 以及 $5 给顾客

选择第二种方案的原因对于做生意的老板应该不陌生,营业过程中我们需要备上一部分零钱在交易时方便找零,不至于出现无法找零的尴尬局面,这是商人们所想的,在上题中也同样适用。
但贪心算法的弊端也很明显:不考虑之前解带来的影响,仅仅为了达到当前最优解,这样”一根筋“的策略也不能在任何情况下得到最优解。
如只有面值分别为 1、5 和 11 单位的硬币,而希望找
回总额为 15 单位的硬币。按贪婪算法,应找 1 个 11 单位面值的硬币和 4 个 1 单
位面值的硬币,共找回 5 个硬币。但最优的解应是 3 个 5 单位面值的硬币。

这里使用贪心算法可以得到我们较为满意的解:具体做法如下↓

使用几个变量进行记录:

static int boxSize;//每个箱子的大小
static int n;//共 n 个物品
static int useBoxNums = 1;//使用箱子的数量
int* cases = reinterpret_cast<int*>(malloc(100 * sizeof(int)));//申请100个int大小的数组

假设现有6个物品体积分别为 5 2 3 4 5 6 需要用体积为 6 的箱子装入,箱子数量不限,使用尽可能少的箱子完成任务。
使用一维数组 cases 记录各物品的体积:
在这里插入图片描述

另再创建一个二维数组 loadCondition 记录每个箱子装入物品的情况,最后创建一个一维数组记录着每个箱子装入物品的数量(初始时均为0),作此记录的原因是:在后面的遍历输出结果的时候我们不清楚每个箱子的物品装入数量,而在生成数组时使用了malloc函数仅仅获得了一块连续空间,我们未对其进行初始化,若遍历越界会出现异常导致程序崩溃。
在对数组进行排序时我产生了使用sort函数(包含在 algorithm 头文件下)外加 lambda表达式以简化排序所需要的代码量:

sort(cases[0], cases[n - 1],
		[](int& a, int& b) ->bool {
			return a > b;
		}
	);//对n个物品的体积降序排序

无奈sort内部并未重载传参为普通数组的情况,出现以下异常: 在这里插入图片描述

无奈之下只能手写快排,这也难不倒我,反手就是一个递归版的快速排序,接下来就是很简单的遍历环节了:对排序后的每个物品遍历,依次装入箱中。

具体实现可以参照代码注释,算法思路较为简单,这里不再一一列出,敬请谅解。

实现代码

#include <iostream>
#include <malloc.h>
using namespace std;
static int boxSize;//每个箱子的大小
static int n;//共 n 个物品
static int useBoxNums = 1;//使用箱子的数量
int* cases = reinterpret_cast<int*>(malloc(100 * sizeof(int)));//申请100个int大小的数组
//Holand国旗法快速排序
pair<int, int> holandFlag(int* arr, int start, int end) {
	int i = start - 1, j = end + 1;
	int flag = arr[start];
	int index = start;
	while (index < j) {
		if (arr[index] > flag) swap(arr[++i], arr[index++]);
		else if (arr[index] < flag) swap(arr[--j], arr[index]);
		else index++;
	}
	return make_pair(i, j);
}
//按照降序进行快速排序 
void quickSort(int* arr, int start, int end) {
	if (start >= end) return;//只有一个元素或下标错误时递归结束
	pair<int, int> p = holandFlag(arr, start, end);
	quickSort(arr, start, p.first);
	quickSort(arr, p.second, end);
}

/*           物品体积↓   箱子装入情况↓   箱子装入物品数量↓ */
void loadCases(int** loadCondition, int* countCase) {
	//sort(cases[0], cases[n - 1],
	//	[](int& a, int& b) ->bool {
	//		return a > b;
	//	}
	//);//对n个物品的体积降序排序
	quickSort(cases, 0, n - 1);
	cout << "按照降序排序的物品:" << endl;
	for (int i = 0; i < n; i++)
		cout << cases[i] << "  ";
	cout << endl;
	int curLoadBox = 0;//当前正使用的箱子
	int curBoxSurplus = boxSize;
	for (int i = 0; i < n; i++) {//对这些物品逐一装入
		if (curBoxSurplus >= cases[i]) {//可以装入
			curBoxSurplus -= cases[i];//更新当前箱子剩余容量	
		}
		else {//当前箱子没法装下
			curLoadBox++;//使用下一个箱子
			curBoxSurplus = boxSize - cases[i];//更新该箱子的剩余容量
			useBoxNums++;//计数
		}
		loadCondition[curLoadBox][countCase[curLoadBox]++] = cases[i];
		//更新该箱子的装入情况 : 装了哪些物品以及现在装入物品的数量
	}
}

void printRes(int** loadCondition, int* countCase) {
	for (int i = 0; i < n; i++) {
		if (!countCase[i]) break;//该箱子未装入任何物品,遍历结束
		cout << "第" << i + 1 << "号箱子装入情况如下:" << endl;
		for (int j = 0; j < countCase[i]; j++) {
			cout << j + 1 << " 号物品, 体积为 " << loadCondition[i][j] << endl;
		}cout << endl;
	}
	cout << "共需要 " << useBoxNums << "个箱子" << endl;
}
/*       author : nepu_bin
        bincode.blog.csdn.net            */
int main() {
	cout << "请输入每个箱子的体积:" << endl;
	cin >> boxSize;//每个箱子的可装入的体积
	cout << "请输入需要装入的物品数量(1 ~ 100)" << endl;
	cin >> n;//物品数量
	cout << "请输入这" << n << "个物品的体积情况(1 ~ "<< boxSize <<")注意不可以超过每个箱子的体积哦~" << endl;
	int index = 0;
	while (index < n) {
		cin >> cases[index++];//输入每个箱子的体积情况
	}
	//记录每个箱子的装入情况
	//生成一个可以存放 n 个 int* 类型的一级指针的二级指针
	int** loadCondition = reinterpret_cast<int**>(malloc(n * sizeof(int*)));//n行
	for (int i = 0; i < n; i++) {
		//每个二级指针中存放一个指向n个int大小的一级指针
		loadCondition[i] = reinterpret_cast<int*>(malloc(n * sizeof(int)));
		//极端情况下一个箱子就可以装入这 n 个物品
	}
	//记录每个箱子装入物品的数量,方便后续遍历时不会访问无效元素
	int* countCase = reinterpret_cast<int*> (calloc(n, sizeof(int)));
	//countCase数组初始化每个元素为0  calloc函数的使用
	loadCases(loadCondition, countCase);
	printRes(loadCondition, countCase);
}

//测试案例:
// 箱子体积为 6
// 共 6 个物品需要放置
//物品体积情况: 5 2 3 4 5 6 

运行效果

在这里插入图片描述

有需要改进或是不对的地方还请大家一起优化、改正,小的接受批评。OvO~~~



这篇关于贪心算法之装箱问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程