0-1背包问题(回溯法)

01 背包问题是什么？

问题描述：

有n个物品

每个物品：

重量w[i]

价值v[i]

背包容量为W

每个物品只能选 0 次或 1 次（这就是 “01” 的由来）

目标：
在不超过背包容量的前提下，使总价值最大

举个直观例子

背包容量W = 4

选 1 + 2 → 重量 4，价值 35

只选 3 → 价值 30

最优答案：35

01 背包的回溯法在干什么？

一句话版：

回溯法 = 枚举所有“选 / 不选”的可能，通过搜索树找最优解

本质是：

深度优先搜索（DFS）

穷举解空间

用剪枝减少搜索量

注意：
回溯法不是最终高效解法，而是：

理解问题本质

讲解 DP 推导的“母体”

回溯视角下的 01 背包

每个物品只有两个选择

对第i个物品：

要么选
要么不选
所以整个问题就是一棵二叉决策树

决策树长什么样？

假设有 3 个物品：

物品1
/ \
不选 选
物品2 物品2
/ \ / \
不选 选 不选 选
物品3 物品3 物品3 物品3

树深度 = 物品个数n

每一条从根到叶子的路径 = 一种方案

叶子节点 = 一种完整选择

回溯 = 在这棵树上走、试、退

代码：

class Knapsack { private: int n; // 物品个数 double c; // 背包容量 vector<double> W; // 重量 vector<double> V; // 价值 double cw; // 当前重量 double cv; // 当前价值 double bestv; // 最优价值 void backtrace(int i) { // 所有物品都考虑完了 if (i == n) { if (cv > bestv) bestv = cv; return; } // 1️⃣ 不选第 i 个物品 backtrace(i + 1); // 2️⃣ 选第 i 个物品（前提是不超重） if (cw + W[i] <= c) { cw += W[i]; cv += V[i]; backtrace(i + 1); // 回溯 cw -= W[i]; cv -= V[i]; } } public: double getMaxVal(const vector<double>& w, const vector<double>& v, double cc) { W = w; V = v; n = W.size(); if (n == 0 || n != V.size()) return 0; c = cc; cw = 0; cv = 0; bestv = 0; backtrace(0); return bestv; } };