1. 前言

背包问题是类型问题，通过对这一类型问题的理解和掌握，从而可以归纳出求解此类问题的思路和模板。

背包问题的分类有：

• 0-1背包问题，也称为不可分割背包问题。
• 无限背包问题。
• 判定性背包问题.
• 带附属关系的背包问题。
• 双背包求最优值.
• 构造三角形问题.
• 带上下界限制的背包问题(012背包)
• ……

本文将介绍0-1背包问题的各种求解方案，通过对各种求解方案的研究，从而全方面了解0-1背包问题的本质。

2. 0-1 背包问题

问题描述：

有一背包，能容纳的重量为 m，现有 n种物品，每种物品有重量和价值 2 个属性。请设计一个算法，在不分割物品的情况下，保证背包中所容纳的物品的总价值是最大的。

0-1背包也称为完全背包或不可分割背包问题，是一类常见的背包问题。常用的实现方案有递归和动态规划 。

2.1 递归算法

可以有 3 种写法。

2.1.1 第一种递归回溯方案

回顾递归回溯算法适合的问题域：

• 待解决的问题可以分多步。如迷宫问题、排列组合问题……
• 每一步都可能存在多个选择，当某一个选择行不通，或此选择结束后，可以回溯到上一步再另行选择。

那么背包问题是否适合上述的要求？

• 可以想象背包里有很多个格间。当每一个格间填充完毕，则表示得到一种求解。
• 对于格间而言，每一种物品都是一种选择，可以通地回溯再选择另一个物品。
• 其本质是对物品进行任意组合，然后再选择总价值最大的一种组合。

如下图，有 3 个物品需要放置入容量为 50 的背包中。初始可把背包想象成一个大格间，此时可以试着放入物品中的一个。

物品放入格间的条件：

• 物品不曾在背包中。
• 物品的重量小于或等于背包现有容量。

如下图，把物品一放入背包中。且把背包剩下空间想象为一个格间，在余下的物品中选择一个放入此格间中。

如下，把物品二放入格间中。

因物品一和物品二的重量之和为 50。等于背包总容量。此时，背包中已经没有剩余空间。也意味着不能再向此背包中放入物品。

至此，可以输出背包中的物品，且把背包中的总价值 180 存储在全局变量中，以便在后续操作时，查找是否还有比此值更大的值。

回溯物品

所谓回溯物品，指把物品从背包中移走，试着再放入一个其它物品。

如下图，回溯物品二，腾出格间。因物品三满足放入条件，放入格间。

此时，背包还有剩余空间，同样把剩余空间想象成一个格间。因有剩余空间，可以试着把物品二放入背包中。

但因物品二的重量大于背包已有的容量，不能放入。此时，可以输出背包中的物品信息，并记录背包中的最大价值为110。因比前面的180的值小，继续保留 180这个价值为当前最大值。

对上述流程做一个简单总结：

• 当背包还有空间，且有物品可以放入时，则加入到背包中。

• 当背包不再能放下任何一件物品时，计算此时的总价值，并确定是不是最大价值。

  Tips：这里有一点需要注意，递归函数的出口有 2 个，一是还有物品可选择，但不能放入背包中。二是不再有物品可供选择。

• 回溯当前已经放入物品，选择其它物品，重复上述过程，一直到找到真正的最大值。

代码如下所示：

#include
using namespace std;
struct Goods {//重量int weight;//价值int price;//装入状态bool isUse;
};
/*
*初始化
*/
Goods allGoods[3]= { {20,60,false},{30,120,false},{10,50,false}};//背包重量
int weight=50;
//最大价值
int maxPrice=0;
//总价值
int totalPrice=0;
/*
* 0-1 背包
* idx:物品编号，只需要考虑组合
* deep:递归深度
*/
void bag(int idx,int deep,int weight) {//每次都可以从所有物品中进行选择for(int i=idx; i<3; i++) {if( allGoods[i].isUse==false  ) {//物品不曾放入背包if( allGoods[i].weight<=weight) {//且可以放下，增加背包中的总价值totalPrice+=allGoods[i].price;//标志此物品已经放入allGoods[i].isUse=true;//继续放置物品bag(i,deep+1,weight - allGoods[i].weight);//回溯totalPrice-=allGoods[i].price;allGoods[i].isUse=false;} else {//出口一：不可以放下，计算此时背包中的物品的价值是否是最大值，cout<<"-----------查询到某个物品不能放下时，显示背包中信息------------"<maxPrice) maxPrice= totalPrice;for(int j=0; j<3; j++)if(allGoods[j].isUse)cout<maxPrice) maxPrice= totalPrice;cout<<"此时背包中物品"<

#include
using namespace std;
struct Goods {//物品重量int weight;//物品价值int value;//物品状态 1 已经使用，0 未使用int isUse;
};//最大价值
int maxPrice=0;
//总价值
int totalPrice=0;
//背包重量
int bagWeight=100;
//物品信息
Goods allGoods[5]= { {20,60,false},{30,120,false},{10,50,false},{20,20,false},{40,100,false} };
int count=4;
/*
*显示背包中物品
*/
void showBag() {for(int i=0; i<5; i++) {if(allGoods[i].isUse)cout<=0 ) {//物品状态allGoods[idx].isUse=i;//总价值totalPrice+=allGoods[idx].value*i;if(idx==4) {if(totalPrice>maxPrice) {maxPrice=totalPrice;cout<<"------------"<

#include
#include//max函数
using namespace std;
struct Goods {//重量int weight;//价值int price;//装入状态bool isUse;
};
//所有物品
Goods allGoods[5]= { {20,60,false},{30,120,false},{10,50,false},{20,20,false},{40,100,false} };
//背包重量
int bagWeight = 100;
//物品总数量
int totalNumber = 5;
/*
*递归
*/
int zeroAndOneBag(int index, int remainWeight) {int totalPrice = 0;//没有物品可放if (index == totalNumber) return 0;if (allGoods[index].weight > remainWeight)//当前物品不能放入，查看其它物品放入的情况totalPrice = zeroAndOneBag(index + 1, remainWeight);else//当前物品可以放入，则在把此物品放入和不放入背包时的最大价值 totalPrice = max(zeroAndOneBag(index + 1, remainWeight -allGoods[index].weight) + allGoods[index].price, zeroAndOneBag(index + 1, remainWeight));return totalPrice;
}
//测试
int main() {int value = zeroAndOneBag(0, bagWeight);cout << value << endl;return 0;
}

#include 
#include 
using namespace std;
int main(int argc, char** argv) {//物品信息int goods[3][3]= { {1,4},{2,3} };//背包容量int bagWeight=0;cout<<"请输入背包容量："<>bagWeight;//状态表int db[4][bagWeight+1]= {0};for(int i=0; i<4; i++) {for(int j=0; jwt ) {//如果背包不能装下物品，保留背包上一次的结果db[w][wt]=db[w-1][wt];} else {//能装下,计算本物品价值和剩余容量的最大价值int val=goods[w-1][1] + db[w-1][ wt- goods[w-1][0] ];//背包原来的价值int val_= db[w-1][wt];//计算最大值db[w][wt]=val>val_?val:val_;}}}for(int i=1; i<3; i++) {for(int j=1; j<=bagWeight; j++) {cout<