先进先出队列分支限界法求解0/1背包箱问题c++代码
时间: 2023-06-26 07:06:58 浏览: 52
以下是使用先进先出队列分支限界法求解0/1背包问题的C++代码。
```c++
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int level; // 当前节点在树中的层数
int profit; // 当前节点的价值
int weight; // 当前节点的重量
double bound; // 当前节点的上界
};
struct cmp {
bool operator()(const Node& a, const Node& b) {
return a.bound < b.bound;
}
};
int n; // 物品数量
int c; // 背包容量
int* w; // 物品重量数组
int* p; // 物品价值数组
int knapsack() {
priority_queue<Node, vector<Node>, cmp> Q; // 使用优先队列维护扩展节点
Node u, v;
u.level = -1; // 根节点的 level 为 -1
u.profit = 0;
u.weight = 0;
u.bound = 0;
int maxProfit = 0;
Q.push(u);
while (!Q.empty()) {
u = Q.top(); // 选取优先级最高的节点进行扩展
Q.pop();
if (u.level == -1) {
v.level = 0;
} else if (u.level != n - 1) {
v.level = u.level + 1;
}
v.weight = u.weight + w[v.level]; // v 为左儿子节点,选择第 v.level 个物品
v.profit = u.profit + p[v.level];
if (v.weight <= c && v.profit > maxProfit) {
maxProfit = v.profit;
}
v.bound = (double) v.profit + (double) (c - v.weight) * p[v.level + 1] / w[v.level + 1];
if (v.bound > maxProfit) {
Q.push(v);
}
v.weight = u.weight; // v 为右儿子节点,不选择第 v.level 个物品
v.profit = u.profit;
v.bound = (double) v.profit + (double) (c - v.weight) * p[v.level + 1] / w[v.level + 1];
if (v.bound > maxProfit) {
Q.push(v);
}
}
return maxProfit;
}
int main() {
cout << "请输入物品数量和背包容量:" << endl;
cin >> n >> c;
w = new int[n];
p = new int[n];
cout << "请输入每个物品的重量和价值:" << endl;
for (int i = 0; i < n; i++) {
cin >> w[i] >> p[i];
}
cout << "能够装入背包的最大价值为:" << knapsack() << endl;
delete[] w;
delete[] p;
return 0;
}
```
在这个代码中,使用了优先队列来维护待扩展节点,其中cmp是一个比较结构体,用于比较两个节点的上界大小,从而维护优先队列。在每次循环中,选取优先级最高的节点进行扩展,计算其左儿子节点和右儿子节点的上界,并将上界大于当前最大价值的节点加入优先队列中。在计算上界时,使用了松弛约束的思想,即将未考虑的物品按单位重量价值从大到小排序,然后依次将物品加入背包,直到背包容量已满为止。最后得到的就是该节点的上界。