)
01 背包问题是什么？
问题描述：
有n个物品
每个物品：
重量w[i]
价值v[i]
背包容量为W
每个物品只能选 0 次或 1 次（这就是 “01” 的由来）
目标：
在不超过背包容量的前提下，使总价值最大
举个直观例子
| 物品 | 重量 | 价值 |
|---|---|---|
| 1 | 1 | 15 |
| 2 | 3 | 20 |
| 3 | 4 | 30 |
背包容量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; } };
)
