[数据结构与算法]背包问题（Knapsack Problem）—— 0/1 背包问题 —— 总价值最大问题

0/1背包问题（0/1 Knapsack Problem）

“0/1”的意思是：每个物品只会放入背包零个或者一个。一个物品只能整个放入背包，要不就不放入背包。物品是无法切割的。

0/1背包问题的关键点，在于如何有效利用背包剩余重量，找出最好的物品组合方式。0/1背包问题是经典的 NP-complete 问题，无法快速求得精确解，只能折衷求得近似解。然而，当数值范围不大时，可以用动态规划快速求得精确解。

让背包里物品总价值最大

这也是 0/1 背包问题的最常见问题。

我们可以知道对于第 $i$ 件物品而言，我们有两个选择：选或者不选。使用动态规划的思想，这样我们可以得出如下的状态转移方程：

• 当我们不选择第

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系

了解本专栏 订阅专栏 解锁全文 超级会员免费看