介绍
给定 n 个物品和一个容量为 C 的背包，物品 i 的重量为
，其值为
问：我应该如何选择放入背包的物品，使得背包中物品的总价值最大化？
背包问题是一个具有多种应用的组合优化问题
背包问题
在背包问题中，我们有一组物品。每件物品都有一个重量和一个价值：
背包算法示例.png
我们想把这些物品放进背包。但是，背包有重量限制：
无标题文件 (2).png
因此我们需要选择总重量不超过限重，且总价值达到最高的物品，比如上例最佳方案是选择5kg和6kg的物品，限重内最大价值为40元。
背包问题有几种变体。