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。

0/1背包问题回溯法的C++代码

以下是一个使用回溯法解决0/1背包问题的简单示例代码：

#include <iostream>
#include <vector>

using namespace std;

int maxWeight = 0; // 最大重量
vector<int> curItems; // 当前选择的物品
vector<int> bestItems; // 最优选择的物品

void backtrack(int currentIndex, int currentWeight, int capacity, vector<int>& weights) {
    if (currentIndex >= weights.size() || currentWeight == capacity) {
        if (currentWeight > maxWeight) {
            maxWeight = currentWeight;
            bestItems = curItems;
        }
        return;
    }

    if (currentWeight + weights[currentIndex] <= capacity) {
        curItems.push_back(weights[currentIndex]);
        backtrack(currentIndex + 1, currentWeight + weights[currentIndex], capacity, weights);
        curItems.pop_back();
    }

    backtrack(currentIndex + 1, currentWeight, capacity, weights);
}

int main() {
    vector<int> weights = {2, 3, 4, 5}; // 物品重量
    int capacity = 7; // 背包容量

    backtrack(0, 0, capacity, weights);

    cout << "最大重量: " << maxWeight << endl;
    cout << "最优选择的物品: ";
    for (int item : bestItems) {
        cout << item << " ";
    }
    cout << endl;

    return 0;
}

这段代码使用递归回溯的方法，通过枚举每个物品的选择情况来求解0/1背包问题。在回溯过程中，维护当前选择的物品和当前总重量，并根据约束条件进行剪枝。最后输出最大重量和最优选择的物品。注意，这只是一个简单的示例代码，实际问题中可能需要考虑更多因素和优化策略。