01背包问题回溯法c++

以下是 01背包问题 的回溯法 C++ 代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[1010],v[1010];
int ans=0;
void dfs(int now,int tw,int tv){//now为当前物品编号，tw为当前已选物品重量，tv为当前已选物品价值
    if(now==n+1){//已选完所有物品
        if(tw<=m){//当前方案合法
            ans=max(ans,tv);//更新答案
        }
        return;
    }
    dfs(now+1,tw,tv);//不选当前物品
    dfs(now+1,tw+w[now],tv+v[now]);//选当前物品
}
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;
}

该代码使用了深度优先搜索的思想，通过对每个物品的选与不选进行穷举，得到所有可能的方案，并在每次得到新方案时更新最优解。

相关问题

c++01背包问题回溯法

01背包问题是一个经典的动态规划问题，但是也可以用回溯法来解决。

具体思路是：从第一个物品开始，依次考虑是否将其放入背包中，如果放入，则将背包容量减少相应的重量，继续考虑下一个物品；如果不放入，则直接考虑下一个物品。当考虑完所有物品时，记录当前背包中的价值，与已知的最大价值进行比较，更新最大价值。

下面是C++代码实现：

#include <iostream>
using namespace std;

int N, W;
int w[100], v[100];
int maxValue = 0;

void backtrack(int i, int weight, int value) {
    if (i == N) {
        if (value > maxValue) {
            maxValue = value;
        }
        return;
    }
    if (weight + w[i] <= W) {
        backtrack(i+1, weight+w[i], value+v[i]); // 放入第i个物品
    }
    backtrack(i+1, weight, value); // 不放第i个物品
}

int main() {
    cin >> N >> W;
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
    backtrack(0, 0, 0);
    cout << maxValue << endl;
    return 0;
}

其中，backtrack函数的参数含义分别为：当前考虑到的物品编号i，当前背包中已经装的物品重量weight，当前背包中已经装的物品价值value。

回溯法01背包问题c++代码

回溯法是解决01背包问题的一种常见方法。具体思路是对于每个物品，选择装入或不装入背包，直到将所有物品都遍历完毕。这种方法需要遍历所有可能的情况，因此时间复杂度较高，但是可以得到最优解。

以下是一个简单的C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

int max_weight = 0; //最大承重量
vector<int> weights; //物品重量
vector<int> values; //物品价值
vector<bool> selected; //是否选中该物品

void backtrack(int curr_weight, int curr_value, int index) {
    if (curr_weight > max_weight) { //超过承重量，直接返回
        return;
    }
    if (index == weights.size()) { //所有物品都遍历完毕
        if (curr_value > max_value) { //更新最大价值
            max_value = curr_value;
        }
        return;
    }
    //不选该物品
    backtrack(curr_weight, curr_value, index + 1);
    //选该物品
    selected[index] = true;
    backtrack(curr_weight + weights[index], curr_value + values[index], index + 1);
    selected[index] = false; //回溯
}

int main() {
    int n; //物品数量
    cin >> n;
    cin >> max_weight;
    for (int i = 0; i < n; i++) {
        int w, v;
        cin >> w >> v;
        weights.push_back(w);
        values.push_back(v);
        selected.push_back(false);
    }
    backtrack(0, 0, 0);
    cout << max_value << endl;
    return 0;
}