背包

背包问题

定义

背包问题 (Knapsack problem) 是一种组合优化的 NP 完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

——百度百科

分类

• 01 背包：有 N 件物品和一个容量为 V 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。每样物品可取1件
• 完全背包：有 N 种物品和一个容量为 V 的背包，每种物品都有 无限 件可用。第 i 种物品的体积是 c，价值是 w。将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
• 多重背包：有 N 种物品和一个容量为 V 的背包。第 i 种物品最多 有 n 件 可用，每件体积是 c，价值是 w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

01 背包

问题

有 N 件物品和一个容量为 V 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

思路

每样物品最多可以取1次，即对于每样物品只有 取 或 不取 两种状态。