01 背包问题是什么问题描述有n个物品每个物品重量w[i]价值v[i]背包容量为W每个物品只能选 0 次或 1 次这就是 “01” 的由来目标在不超过背包容量的前提下使总价值最大举个直观例子物品重量价值111523203430背包容量W 4选 1 2 → 重量 4价值 35只选 3 → 价值 30最优答案3501 背包的回溯法在干什么一句话版回溯法 枚举所有“选 / 不选”的可能通过搜索树找最优解本质是深度优先搜索DFS穷举解空间用剪枝减少搜索量注意回溯法不是最终高效解法而是理解问题本质讲解 DP 推导的“母体”回溯视角下的 01 背包每个物品只有两个选择对第i个物品要么选要么不选所以整个问题就是一棵二叉决策树决策树长什么样假设有 3 个物品物品1/ \不选 选物品2 物品2/ \ / \不选 选 不选 选物品3 物品3 物品3 物品3树深度 物品个数n每一条从根到叶子的路径 一种方案叶子节点 一种完整选择回溯 在这棵树上走、试、退代码class Knapsack { private: int n; // 物品个数 double c; // 背包容量 vectordouble W; // 重量 vectordouble 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 vectordouble w, const vectordouble 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; } };