01 背包
有 n 件物品，与一次最多能背 w 重量的背包。第 i 件物品，重量为 weight[i]，得到的价值为 value[i]。
每件物品只能用一次，求解，将那些物品装入背包内，物品的价值总和最大。
| 重量 (weight) | 价值 (value) | |
|---|---|---|
| 物品 0 | 1 | 15 |
| 物品 1 | 3 | 20 |
| 物品 2 | 4 | 30 |
这是一个标准的背包问题。很多一看到这个，就直接想起用动态规划，而忽略了暴力解法。
这是因为没有自下而上思考的结果。
如下代码，一般动态规划问题，都是能通过回溯解决，因为每个物品都有两种可能（状态），被放入背包，或者不放入背包。
// 全局变量用于记录最大价值
int maxValue = 0;
// 物品的重量和价值数组
vector<int> weights = {1, 3, 4, 5, 6};
vector<int> values = {1, 3, 4, 5, 6};
// 背包容量
int capacity = 10;
// 回溯函数
void backtrack(int index, int currentWeight, int currentValue) {
// 如果已经遍历完所有物品
if (index == weights.size()) {
// 更新最大价值
if (currentValue > maxValue) {
maxValue = currentValue;
}
return;
}
// 不选择当前物品 - 01 背包中的 0
backtrack(index + 1, currentWeight, currentValue);
// 选择当前物品 - 01 背包中的 1
(currentWeight + weights[index] <= capacity) {
(index + , currentWeight + weights[index], currentValue + values[index]);
}
}
