【回溯法解决01背包问题】

(文章目录)

什么是01背包问题？

01背包问题描述在给定容量的背包中选择一组物品以最大化总价值的问题。每个物品都有一个重量和一个价值，背包有一个固定的容量。问题的目标是找到一组物品，使其总重量不超过背包容量，同时总价值最大化。

回溯法的基本思想

回溯法是一种解决组合优化问题的常见方法。它基于深度优先搜索（DFS）的思想，尝试在问题空间中搜索所有可能的解，并在搜索过程中进行剪枝，以排除不可能达到最优解的分支。在01背包问题中，回溯法的基本思想如下：

1. 从第一个物品开始，考虑将它放入背包或不放入背包两种选择。
2. 如果放入背包不超过背包的容量，并且总价值更高，那么选择放入背包，继续考虑下一个物品。
3. 如果不放入背包或者放入背包但超过容量，那么选择不放入背包，继续考虑下一个物品。
4. 递归地对每个物品进行上述选择，直到考虑完所有物品或达到背包容量。
5. 在搜索过程中记录当前的总价值，并比较最大总价值。

C++示例代码

#include <iostream>
#include <vector>

using namespace std;

int knapsack(int capacity, vector<int>& weights, vector<int>& values, int index) {
    if (index == 0 || capacity == 0) {
        return 0;
    }

    if (weights[index - 1] > capacity) {
        return knapsack(capacity, weights, values, index - 1);
    } else {
        int include = values[index - 1] + knapsack(capacity - weights[index - 1], weights, values, index - 1);
        int exclude = knapsack(capacity, weights, values, index - 1);
        return max(include, exclude);
    }
}

int main() {
    vector<int> weights = {2, 3, 4, 5};
    vector<int> values = {3, 4, 5, 6};
    int capacity = 5;

    int max_value = knapsack(capacity, weights, values, weights.size());

    cout << "Maximum value: " << max_value << endl;

    return 0;
}