分支界限——01背包问题
01背包问题
背包问题是著名的NP完全问题，在实际生活中有广泛的应用。01背包是背包问题中的一种，也是较简单的一种，有很多种算法可以求解01背包问题，这里介绍利用分支界限的算法。
问题描述
设有n个物品，他们具有各自的重量w和价值v；给定一个具有一个容量W的背包，求将物品有选择的放入背包中，使得装入的物品的价值之和最大？
01背包：物品是完整个体，只存在放或不放两种状态，不能放入一部分。
分析设计
01背包可以通过动态规划的思想求解，详见博客
现在我们通过分支界限的思想进行求解。
- 首先我们先将要放入背包的物品按照单位价值进行排序，单位价值 A i = v i / w i A_i=v_i/w_i Ai=vi/wi；
- 选择边界(上界)函数： U b = v + ( W − w ) ( v i + 1 / w i + 1 ) Ub=v+(W-w)(v_{i+1}/w_{i+1}) Ub=v+(W−w)(vi+1/wi+1)；即：已经选择物品的总价值v+背包的剩余承重W-w与剩下物品的最佳单位回报vi+1/wi+1的乘积；
- 在选取物品时，均存在两种情况，放入或不放入，则比较另种情况下的上界Ub，选择Ub较大的情况，注意，在选择放入时还需要考虑是否能够放入，即背包仍有足够大的空间；
- 重复2、3步直到所有物品均有所选择。
在计算平均单位价值时，我们每次取出的是单位价值最高的一个，我们可以采用排序的方法顺序取出，但在这里，我们采用的是优先队列的数据结构。利用VS当中已有的优先队列（也可以自己写），将物品结点按照单位价值降序放入队列当中，每次取出队首位置的结点即可。
在上界Ub的计算中，我们需要将其进行初始化，一开始还没有放入任何物品时，上界即为最最理想的状态，即全部放入单位价值最高的物品，且刚好装满背包，所以， U b = W ∗ a v e m a x Ub=W*ave_{max} Ub=W∗avemax，这里ave表示单位价值。
源代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//物品
typedef struct goods {
int item; //物品名称
int weight; //重量
int value; //价值
int ave; //平均价值=价值/重量
};
//运算符重载，优先队列降序排列
typedef struct temp {
bool operator()(goods a, goods b) {
return a.ave < b.ave;
}
};
priority_queue < goods, vector<goods>, temp> q;
void Knapsack(int W) {
vector<bool> choose(q.size() + 1, false); //物品是否选择放入背包
int ub = q.top().ave*W; //初始化上界
int w = 0, v = 0; //当前背包里的重量w，价值v
while (!q.empty()){
if (w + q.top().weight > W) {
q.pop();
if (!q.empty())
ub = v + q.top().ave*(W - w);
continue;
}
goods a = q.top(); //取出队首位置的物品
q.pop();
if (!q.empty()) {
int yes = v + a.value + q.top().ave*(W - w - a.weight); //放入物品
int no = v + q.top().ave*(W - w); //不放物品
if (yes > no) {
ub = yes;
w += a.weight;
v += a.value;
choose[a.item] = true;
}
else
ub = no;
}
else {
v += a.value;
choose[a.item] = true;
}
}
cout << "背包最大价值为：" << v << endl;
cout << "装入的物品编号为：";
for (int i = 1; i < choose.size(); i++)
if (choose[i])
cout << i << " ";
cout << endl;
}
int main() {
int n, W;
cout << "输入物品个数：";
cin >> n;
cout << "输入背包容量：";
cin >> W;
vector<goods> package(n);
cout << "输入物品信息：（重量w 价值w）" << endl;
for (int i = 0; i < n; i++) {
package[i].item = i + 1;
cin >> package[i].weight >> package[i].value;
package[i].ave = package[i].value / package[i].weight;
q.push(package[i]); //存入信息入队
}
Knapsack(W); //01背包
system("pause");
return 0;
}
/*
3 12
7 42
5 25
4 40
*/
