贪心算法之装箱问题
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~~~
这篇关于贪心算法之装箱问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南