回溯法01背包问题c++

回溯法是一种解决组合优化问题的通用算法，它适用于诸如0/1背包问题这样的动态规划问题。01背包问题是一个经典的计算机科学问题，给定一组物品，每种物品有自己的重量和价值，目标是在不超过背包容量的前提下，选择一种组合以获取最大的总价值。

在C++中，你可以通过以下几个步骤实现回溯法求解01背包问题：

1. 定义数据结构：包括物品列表、背包容量、当前选中的物品集合和最大价值。

2. 创建递归函数`backtrack()`：
- 初始化函数时，设置当前选择的物品集合为空，总价值为0。
- 对于每个物品，有两种情况：放入背包和不放入背包。
- 如果放入口袋，计算新的总价值并检查是否超过背包容量。如果未超限，更新最大价值和物品集合，并继续对剩余物品进行递归搜索。
- 如果不放入口袋，直接对下一个物品进行递归，因为已经考虑了放入的情况。
- 当所有物品都遍历完，返回是否达到最大价值。

3. 主函数中调用`backtrack()`，传递初始条件（空背包和所有物品），并初始化结果变量。

4. 结果判断：在递归结束时，如果没有找到符合条件的结果，返回0；否则返回最大价值。

#include <vector>
using namespace std;

int knapsack(vector<pair<int, int>>& items, int W, int n) {
    vector<vector<bool>> dp(n + 1, vector<bool>(W + 1, false));
    bool backtrack(int index, int capacity) {
        if (index == n || capacity == 0) return dp[index][capacity] = 0;
        dp[index][capacity] = max(
            items[index].second + backtrack(index + 1, capacity),
            backtrack(index + 1, capacity - items[index].first)
        );
        return dp[index][capacity];
    }
    return backtrack(0, W);
}

// 示例：
int main() {
    vector<pair<int, int>> items = {{60, 100}, {100, 200}, {120, 300}};
    int W = 500; // 背包容量
    int n = items.size();
    cout << "最大价值为: " << knapsack(items, W, n) << endl;
    return 0;
}