回溯应用-- 0-1背包问题
1. 问题描述
0-1背包非常经典，很多场景都可以抽象成这个问题。经典解法是动态规划，回溯简单但没有那么高效。
- 有一个背包，背包总的承载重量是 W kg。现有n个物品，每个物品重量不等，并且不可分割。
- 选择几件物品，装到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品总重量最大？
- 物品是不可分割的，要么装要么不装，所以叫 0-1背包问题。
2. 回溯解决思路
- 对于每个物品来说，都有两种选择，装进背包或者不装进背包。
- 对于n个物品来说，总的装法就有 2n 种，去掉总重量超过 W kg的，从剩下的装法中选择总重量最接近 W kg的。不过，我们如何才能不重复地穷举出这 2n 种装法呢？
可以用回溯方法。
- 把物品依次排列，整个问题就分解为了n个阶段，每个阶段对应一个物品怎么选择。
- 先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。
- 当发现已经选择的物品的重量超过 W kg之后，就停止继续探测剩下的物品(搜索剪枝技巧)。
/**
* @description: 0-1背包--回溯应用
* @author: michael ming
* @date: 2019/7/9 1:13
* @modified by:
*/
#include <iostream>
#define MaxWeight 76 //背包承载极限
using namespace std;
void fill(int i, int curWeight, int *bag, int N, int &maxweightinbag)
{
if(curWeight == MaxWeight || i == N)//到达极限了，或者考察完所有物品了
{
if(curWeight > maxweightinbag)
maxweightinbag = curWeight;//记录历史最大装载量
return;
}
fill(i+1,curWeight,bag,N,maxweightinbag);//不选择当前i物品，cw不更新
if(curWeight+bag[i] <= MaxWeight)//选择当前i物品，cw更新
{//没有达到极限，继续装
fill(i+1,curWeight+bag[i],bag,N,maxweightinbag);
}
}
int main()
{
const int N = 4;
int bag[N] = {15,6,40,21};
// int bag[N] = {1,2,3,4};
int maxweightinbag = 0;
fill(0,0,bag,N,maxweightinbag);
cout << "最大可装进背包的重量是：" << maxweightinbag;
return 0;
}升级版： 每个物品对应着一种价值，求不超过背包载重极限，可装入背包的最大总价值。（在上面程序里稍加修改即可）
/**
* @description:
* @author: michael ming
* @date: 2019/7/11 20:42
* @modified by:
*/
#include <iostream>
#define MaxWeight 50 //背包承载极限
using namespace std;
void fill(int i, int curWeight, int curValue, int *bag,int *value, int N, int &weightinbag, int &maxValue)
{
if(curWeight == MaxWeight || i == N)//到达极限了，或者考察完所有物品了
{
if(curValue > maxValue)
{
maxValue = curValue;//记录历史最大价值
weightinbag = curWeight;//记录最大价值对应的重量
}
return;
}
fill(i+1,curWeight,curValue,bag,value,N,weightinbag,maxValue);//不选择当前i物品，cw,cv不更新
if(curWeight+bag[i] <= MaxWeight)//选择当前i物品，cw,cv更新
{//没有达到极限，继续装
fill(i+1,curWeight+bag[i],curValue+value[i],bag,value,N,weightinbag,maxValue);
}
}
int main()
{
const int N = 4;
int bag[N] = {15,6,40,21};
int value[N] = {1,2,3,4};
int weightinbag = 0, maxValue = 0;
fill(0,0,0,bag,value,N,weightinbag,maxValue);
cout << "最大可装进背包的最大价值是：" << maxValue
<< " ,对应重量是: " << weightinbag;
return 0;
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/07/09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
