#include <iostream>
#include <vector>
using namespace std;
// 定义物品结构体
struct Item {
int id;
int weight;
int volume;
int value;
};
// 初始化背包的容量限制
const int MAX_WEIGHT = 50;
const int MAX_VOLUME = 50;
// 全局变量，用于记录最大价值和选择的物品
int maxValue = 0;
vector<Item> selectedItems;
vector<Item> items = {
{1, 10, 20, 60},
{2, 20, 10, 100},
{3, 30, 30, 120},
{4, 25, 15, 70},
{5, 5, 5, 10}
};
// 回溯函数
void backtrack(int index, int currentWeight, int currentVolume, int currentValue, vector<Item>& currentItems) {
// 如果已经考虑了所有物品，则更新最大价值
if (index == items.size()) {
if (currentValue > maxValue) {
maxValue = currentValue;
selectedItems = currentItems;
}
return;
}
// 不选择当前物品
backtrack(index + 1, currentWeight, currentVolume, currentValue, currentItems);
// 如果当前物品可以被选择（不超过背包容量）
if (currentWeight + items[index].weight <= MAX_WEIGHT &&
currentVolume + items[index].volume <= MAX_VOLUME) {
// 选择当前物品
currentItems.push_back(items[index]);
backtrack(index + 1, currentWeight + items[index].weight, currentVolume + items[index].volume,
currentValue + items[index].value, currentItems);
// 回溯，撤销选择
currentItems.pop_back();
}
}
int main() {
// 初始化物品列表
vector<Item> items = {
{1, 10, 20, 60},
{2, 20, 10, 100},
{3, 30, 30, 120},
{4, 25, 15, 70},
{5, 5, 5, 10}
};
// 调用回溯函数
vector<Item> currentItems;
backtrack(0, 0, 0, 0, currentItems);
// 输出最大价值和选择的物品
cout << "Maximum value: " << maxValue << endl;
cout << "Selected items:" << endl;
for (const auto& item : selectedItems) {
cout << "Item ID: " << item.id << ", Weight: " << item.weight << ", Volume: " << item.volume << ", Value: " << item.value << endl;
}
return 0;
}
标签：index,currentValue,背包,10,int,items,算法,currentItems,多维 From： https://blog.csdn.net/m0_63846601/article/details/136942595