用限界剪枝法解01背包问题C++
时间: 2024-03-21 13:34:37 浏览: 45
以下是使用限界剪枝法解决01背包问题的C++代码示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 定义物品结构体
struct Item {
int weight;
int value;
};
// 计算当前节点的上界
int calculateUpperBound(int currentWeight, int remainingCapacity, const vector<Item>& items) {
int upperBound = 0;
int n = items.size();
int i = currentWeight + 1;
// 将剩余容量填满
while (i < n && items[i].weight <= remainingCapacity) {
remainingCapacity -= items[i].weight;
upperBound += items[i].value;
i++;
}
// 考虑最后一个物品的部分
if (i < n) {
upperBound += items[i].value * remainingCapacity / items[i].weight;
}
return upperBound;
}
// 使用限界剪枝法解决01背包问题
int knapsack(int capacity, const vector<Item>& items) {
int n = items.size();
vector<int> currentSolution(n, 0); // 当前解
vector<int> bestSolution(n, 0); // 最优解
int currentWeight = 0; // 当前重量
int bestValue = 0; // 最优值
int remainingCapacity = capacity; // 剩余容量
int i = 0;
while (i >= 0) {
// 当前节点的上界
int upperBound = calculateUpperBound(currentWeight, remainingCapacity, items);
// 如果上界小于最优值,则剪枝
if (upperBound < bestValue) {
i--;
continue;
}
// 如果当前节点是叶子节点,则更新最优解
if (i == n - 1) {
if (currentWeight + items[i].weight <= capacity) {
currentSolution[i] = 1;
currentWeight += items[i].weight;
bestValue = 0;
for (int j = 0; j < n; j++) {
bestSolution[j] = currentSolution[j];
bestValue += currentSolution[j] * items[j].value;
}
}
}
// 如果当前节点不是叶子节点,则继续搜索
else {
if (currentWeight + items[i].weight <= capacity) {
currentSolution[i] = 1;
currentWeight += items[i].weight;
remainingCapacity -= items[i].weight;
i++;
}
else {
currentSolution[i] = 0;
i--;
}
}
}
// 输出最优解
cout << "Best solution: ";
for (int i = 0; i < n; i++) {
cout << bestSolution[i] << " ";
}
cout << endl;
return bestValue;
}
int main() {
// 测试数据
vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};
int capacity = 50;
int maxValue = knapsack(capacity, items);
cout << "Max value: " << maxValue << endl;
return 0;
}
```
相关推荐
![](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)