【回溯法】0-1背包问题 C/C++（附代码）

0-1背包问题的回溯法解决

在这篇文章中已经讨论过0-1背包问题和背包问题的动态规划以及贪心解法，本文将介绍0-1背包问题的回溯法解决

问题描述

给定n种物品和一个容量为C的背包。物品i的重量是wi，其价值为vi。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？

问题分析

0-1背包问题是一个经典的组合优化问题，属于NP完全问题。它可以通过回溯法来解决，回溯法是一种系统地搜索问题解的方法。在回溯法中，我们通过构建解空间树来探索所有可能的解，并通过剪枝策略来减少搜索空间。

子集树

在回溯法中，0-1背包问题可以被看作是一个子集树问题。每个节点代表一个决策点，即是否将当前物品放入背包中。左子树表示将当前物品放入背包，右子树表示不放入背包。

剪枝条件

为了减少搜索空间，我们可以使用以下剪枝条件：

1. 进入左子树的条件：当前物品的重量不超过背包的剩余容量，即 w[i] + cw <= c。
2. 进入右子树的条件：剩余物品的总价值加上当前已放入背包的物品价值之和不小于已有的最大价值，即 r + cv >= best。

（这个问题和装载问题不能说很像吧，起码也是一模一样，代码相似度99%，剩下的1%别忘了背包问题有重量和价值两个量）

代码实现

数据结构

• best：记录当前找到的最大价值。
• bestx[]：记录最优解，即哪些物品被放入背包。
• x[]：记录当前解，即当前路径上哪些物品被放入背包。
• cw：当前背包中物品的总重量。
• cv：当前背包中物品的总价值。
• r：记录剩余物品的总价值，初始值为所有物品的总价值。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#define MAX 100

int n; // 物品数量
int w[MAX]; // 物品重量
int v[MAX]; // 物品价值
int c; // 背包容量
int best = 0; // 最大价值
int bestx[MAX]; // 记录最优解
int x[MAX]; // 当前解
int cw = 0; // 当前重量
int cv = 0; // 当前价值
int r = 0; // 剩余物品的总价值

void backtrack(int i) {
    if (i > n) {
        best = cv;
        for (int j = 1; j <= n; j++) {
            bestx[j] = x[j];
        }
        return;
    }
    r -= v[i];
    if (w[i] + cw <= c) { // 进入左子树
        cw += w[i];
        cv += v[i];
        x[i] = 1;
        backtrack(i + 1);
        cw -= w[i];
        cv -= v[i];
        x[i] = 0;
    }
    if (r + cv >= best) { // 进入右子树
        x[i] = 0;
        backtrack(i + 1);
    }
    r += v[i];
}

int main() {
    cin >> n >> c;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
        r += v[i];
    }
    backtrack(1);
    cout << "最大价值：" << best << endl;
    for (int i = 1; i <= n; i++)
        cout << bestx[i] << " ";
    return 0;
}

代码说明

• 进入下一层结点：在进入下一层结点时，需要将 r 减去当前物品的价值，因为不论这个物品是否放入背包，r 是剩余物品的总价值，都不应该包含当前物品。
• 退回上一层结点：在退回上一层结点时，需要将 r 加回当前物品的价值。
• 剪枝条件：在进入右子树时，已经判断过走右支也可以获得最优解，因此不需要额外判断是否 cw >= bestw。

实例

假设有5件物品，背包容量为10，输入如下：

运行程序后，输出最大价值为15，放入背包的物品为第1、2、5件物品。经验证，该解正确。