回溯法之0/1背包问题

思路:

????????

1. 确定问题类型：由于每个物品只有选或不选两种状态，所以该问题属于 0-1 背包问题。

2. 确定状态表示：由于每个物品只有选或不选两种状态，因此可以使用一个长度为 N 的 01 序列 x 表示选或不选，其中 x[i] = 1 表示选第 i 个物品，x[i] = 0 表示不选第 i 个物品。同时，需要用一个变量 maxv 来记录当前最优解的价值。

3. 确定状态转移方程：对于每个物品 i，有两种情况：选或不选。如果选第 i 个物品，则将背包容量减去 w[i]，同时将总价值加上 v[i]。如果不选第 i 个物品，则直接进入下一个物品的选择过程。这个过程可以使用深度优先搜索（DFS）实现。

4. 添加剪枝条件：在 DFS 过程中，可以添加一些剪枝条件来减少无效搜索。例如，当背包容量已经超过 W 时，可以直接返回上一层；当当前价值小于已经找到的最优解时，也可以直接返回上一层。

5. 输出结果：在 DFS 结束后，可以输出选取的物品和对应的重量和价值，以及总价值。

代码:

#include<iostream>
using namespace std;

const int N = 4; // 物品的数量
const int W = 6; // 背包的容量
int w[] = { 5,3,2,1 }; // 物品的重量数组
int v[] = { 4,4,3,1 }; // 物品的价值数组

int x[N]; // 存放最优解的选择结果
int maxv = 0; // 最大总价值

void dfs(int i, int tw, int tv, int op[]) {
    if (i == N) { // 递归终止条件：已经遍历完所有物品
        if (tw <= W && tv > maxv) { // 检查是否符合背包容量限制，并更新最大总价值
            maxv = tv;
            for (int j = 0; j < N; j++) {
                x[j] = op[j]; // 更新最优解的选择结果
            }
        }
        return; // 返回上一层
    }

    op[i] = 1; // 选择第 i 个物品
    dfs(i + 1, tw + w[i], tv + v[i], op); // 递归调用，考虑选取第 i 个物品的情况
    op[i] = 0; // 不选择第 i 个物品
    dfs(i + 1, tw, tv, op); // 递归调用，不选取第 i 个物品的情况
}

int main() {
    int op[N]; // 存放选择结果的数组
    dfs(0, 0, 0, op); // 将初始状态传入 dfs 函数中，开始递归求解

    cout << "总价值：" << maxv << endl; // 输出最大总价值
    cout << "选择的物品编号：";
    for (int i = 0; i < N; i++) { // 输出最优解的选择结果
        if (x[i] == 1) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}