01背包问题回溯法代码

01背包问题是一个经典的动态规划问题，它的目标是在一组有限的物品中，选择一些物品装入背包，使得背包的总重量不超过限制，同时让背包中物品的总价值最大化。回溯法可以用来解决01背包问题，具体代码如下：

#include <iostream>
using namespace std;

const int MAXN = 1005;
int w[MAXN], v[MAXN];
int n, m, ans;

void dfs(int pos, int cntw, int cntv) {
    if (pos == n + 1) {
        if (cntw <= m && cntv > ans) {
            ans = cntv;
        }
        return;
    }
    dfs(pos + 1, cntw, cntv);
    dfs(pos + 1, cntw + w[pos], cntv + v[pos]);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    dfs(1, 0, 0);
    cout << ans << endl;
    return 0;
}

其中，dfs函数用来进行回溯，pos表示当前考虑到第几个物品，cntw表示当前背包中物品的总重量，cntv表示当前背包中物品的总价值。当pos等于n+1时，表示所有物品已经考虑完毕，此时更新答案。在dfs函数中，每次有两个决策：不选当前物品和选当前物品。当不选当前物品时，dfs(pos+1,cntw,cntv)，即不考虑当前物品，直接考虑下一个物品。当选当前物品时，dfs(pos+1,cntw+w[pos],cntv+v[pos])，即把当前物品放入背包中，考虑下一个物品。