用c++ 回溯法求解0-1背包问题

0-1背包问题是一个经典的动态规划问题，也可以用回溯算法求解，以下是C++的实现代码：

#include <iostream>
#include <vector>
using namespace std;

// 递归回溯求解0-1背包问题
void backtrack(vector<vector<int>>& res, vector<int>& items, vector<int>& selected, int capacity, int start) {
    if(capacity < 0) {
        return;
    }
    if(start == items.size() || capacity == 0) {
        res.push_back(selected);
        return;
    }
    // 不选当前物品
    backtrack(res, items, selected, capacity, start + 1);
    // 选当前物品
    selected[start] = 1;
    backtrack(res, items, selected, capacity - items[start], start + 1);
    selected[start] = 0;
}

vector<vector<int>> solveKnapsack(vector<int>& items, int capacity) {
    vector<vector<int>> res;
    vector<int> selected(items.size(), 0);
    backtrack(res, items, selected, capacity, 0);
    return res;
}

int main() {
    vector<int> items = {2, 3, 4, 5};
    int capacity = 7;
    vector<vector<int>> res = solveKnapsack(items, capacity);
    for(int i = 0; i < res.size(); i++) {
        for(int j = 0; j < res[i].size(); j++) {
            if(res[i][j] == 1) {
                cout << items[j] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

代码思路：
1. 递归函数 backtrack 用于求解 0-1 背包问题，参数 res 表示最终结果，items 表示所有物品的重量，selected 表示当前选中的物品，capacity 表示当前背包的容量，start 表示当前处理的物品编号。
2. 如果当前背包已经装满了或者已经处理完了所有物品，则将结果加入到 res 中，否则分别尝试选取当前物品和不选取当前物品两种情况。
3. 主函数中调用 solveKnapsack 函数求解 0-1 背包问题，并输出结果。