采用回溯法求解0/1背包问题的最优值和最优解用C++实现

好的，以下是一个采用回溯法求解0/1背包问题的最优值和最优解的C++实现：

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 20; //物品数量最大值
const int MAX_W = 100; //背包容量最大值

int n, W; //物品数量、背包容量
int w[MAX_N], v[MAX_N]; //物品重量、价值
int best_v; //最优解的价值
int cur_w, cur_v; //当前解的重量、价值
vector<int> best_sol; //最优解

//回溯函数
void backtrack(int t, vector<int>& cur_sol)
{
    if (t > n)
    {
        if (cur_v > best_v)
        {
            best_v = cur_v;
            best_sol = cur_sol;
        }
        return;
    }
    //不选第t个物品
    cur_sol.push_back(0);
    backtrack(t + 1, cur_sol);
    cur_sol.pop_back();
    //选第t个物品
    if (cur_w + w[t] <= W)
    {
        cur_sol.push_back(1);
        cur_w += w[t];
        cur_v += v[t];
        backtrack(t + 1, cur_sol);
        cur_w -= w[t];
        cur_v -= v[t];
        cur_sol.pop_back();
    }
}

int main()
{
    cout << "请输入物品数量和背包容量：" << endl;
    cin >> n >> W;
    cout << "请输入每个物品的重量和价值：" << endl;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    best_v = 0;
    cur_w = cur_v = 0;
    vector<int> cur_sol;
    backtrack(1, cur_sol);
    cout << "最优解的价值为：" << best_v << endl;
    cout << "最优解为：";
    for (int i = 0; i < best_sol.size(); i++)
        cout << best_sol[i] << " ";
    cout << endl;
    return 0;
}

该程序除了采用了C++语言的特性外，与前面的C语言实现基本相同。不同之处在于，最优解使用了vector<int>类型表示，cur_sol表示当前解。在每次递归时，先尝试不选第t个物品，然后再尝试选第t个物品。如果选了第t个物品，就要更新当前解的重量和价值，并将cur_sol数组中push_back一个1，表示该物品已选中。当t>n时，说明已经枚举完了所有物品，此时如果当前解的价值比最优解的价值更大，就更新最优解的价值和best_sol数组。最后输出最优解的价值和最优解即可。