0/1 Knapsack problem多最优解求解：如何基于DP矩阵生成所有最优解

核心思路是对DP矩阵做分支回溯，而非常规单路径回溯：所有能推导得到当前最优值的选择分支都要遍历，最终收集所有有效路径即可。

具体实现步骤 #

• 首先确定最优解的目标总价值：就是DP矩阵右下角的数值max_val。
• 从DP矩阵右下角（对应「考虑完所有物品、剩余容量为背包最大容量」的状态）开始递归回溯，每个节点判断两种选择的可行性：
  1. 选当前物品：如果当前剩余容量j >= 第i个物品的重量w[i]，且满足dp[i][j] == dp[i-1][j - w[i]] + v[i]，说明选当前物品是能得到最优值的有效路径：将当前物品加入选择列表，递归回溯到「考虑前i-1个物品、剩余容量为j - w[i]」的状态。
  2. 不选当前物品：如果满足dp[i][j] == dp[i-1][j]，说明不选当前物品也能得到最优值，这也是有效路径：不将当前物品加入选择列表，递归回溯到「考虑前i-1个物品、剩余容量仍为j」的状态。
• 边界处理：当回溯到没有物品可考虑时（i < 0），如果当前选择的物品总价值等于max_val，就将当前选择列表存入结果集。
• 回溯还原：递归返回后要把当前物品从选择列表中删除，避免影响其他分支的计算。

针对示例的验证 #

你给出的示例中4个物品重量为[4,2,5,2]、价值为[10,4,10,4]，最大容量7，最优价值14，回溯过程会同时覆盖「选/不选第4个物品」「选/不选第2个物品」等所有符合条件的分支，最终就能得到(1,2)、(1,4)、(2,3)、(3,4)全部4组最优解。

注意事项 #

• 如果物品存在重复的重量、价值，且不需要区分同属性物品的下标，可以将最终结果排序后存入集合去重。
• 物品数量较多时最优解的数量可能指数级增长，可根据实际需求增加剪枝逻辑，比如收集到指定数量的解后提前终止遍历。

内容的提问来源于stack exchange，提问作者AgentSpeed07