01背包分支界限法devc++
时间: 2023-11-26 22:48:29 浏览: 46
以下是01背包问题的分支限界法的C++代码示例,使用Dev C++编译器:
```c++
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct Node {
int level; // 当前节点所在的层数
int profit; // 当前节点的价值
int weight; // 当前节点的重量
double bound; // 当前节点的价值上界
};
bool operator<(const Node& a, const Node& b) {
return a.bound < b.bound;
}
double bound(Node u, int n, int W, int* p, int* w) {
if (u.weight >= W) {
return 0;
}
double bound = u.profit;
int j = u.level + 1;
int totweight = u.weight;
while ((j <= n) && (totweight + w[j] <= W)) {
totweight += w[j];
bound += p[j];
j++;
}
if (j <= n) {
bound += (W - totweight) * p[j] / w[j];
}
return bound;
}
int knapsack(int n, int W, int* p, int* w) {
priority_queue<Node> Q;
Node u, v;
u.level = 0;
u.profit = 0;
u.weight = 0;
u.bound = bound(u, n, W, p, w);
int maxprofit = 0;
Q.push(u);
while (!Q.empty()) {
u = Q.top();
Q.pop();
if (u.bound > maxprofit) {
v.level = u.level + 1;
v.weight = u.weight + w[v.level];
v.profit = u.profit + p[v.level];
if (v.weight <= W && v.profit > maxprofit) {
maxprofit = v.profit;
}
v.bound = bound(v, n, W, p, w);
if (v.bound > maxprofit) {
Q.push(v);
}
v.weight = u.weight;
v.profit = u.profit;
v.bound = bound(v, n, W, p, w);
if (v.bound > maxprofit) {
Q.push(v);
}
}
}
return maxprofit;
}
int main() {
int n = 4;
int W = 8;
int p[] = {0, 2, 3, 4, 5};
int w[] = {0, 1, 2, 3, 4};
int maxprofit = knapsack(n, W, p, w);
cout << "Max profit: " << maxprofit << endl;
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)