背包问题

简介

---

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkel和Hellman提出的。

形式化定义

今$f_{i}\left(x\right) \left(1\le i\le n\right)$为一些函数，Q为一个常数，求出$\left\{x_{1},x_{2},\cdots,x_{n}\right\}$使得：

1. $\sum_{i=1}^{n} x_{i} \le Q$
2. $\sum_{i=1}^{n} f_{i}\left(x_{i}\right)$最大

使用动态规划技术解决

• 01背包

这是最基本的背包问题，每个物品最多只能放一次。

• 完全背包

第二个基本的背包问题模型，每种物品可以放无限多次。

• 多重背包

每种物品有一个固定的次数上限

• 混合背包

将前面三种简单的问题叠加成较复杂的问题

• 二维费用背包

一个简单的常见扩展

• 分组背包问题

一种题目类型，也是一个有用的模型。下一节的基础。

• 有依赖的背包

另一种给物品的选取加上限制的方法。

---

---

练习

USACO中的背包问题

• Translate:USACO/inflate （基本多重背包）
• Translate:USACO/stamps（对初学者有一定挑战性）
• Translate:USACO/money (基本0-1背包)
• Translate:USACO/nuggets
• Translate:USACO/subset （基本0-1背包）
• Translate:USACO/rockers（另一类有趣的“二维”背包问题）
• Translate:USACO/milk4 （很怪的背包问题问法，较难用纯DP求解）