背包问题
- 0-1 背包
- 完全背包
给你一个背包, 它最多可以装载 capacity
的重量, 其中第 i
个物品的重量为 weights[i]
, 价值为 values[i]
. 这个题目中的物品不可以分割, 要么装进包里, 要么不装, 不能说切成两块装一半
, 这就是 0-1
背包的来历. 如以下示例, 最优是可以装载前两个物品, 它的总价值为 6
.
首先明确状态跟选择, 显然状态是重量
给你一个背包, 它最多可以装载 capacity
的重量, 其中第 i
个物品的重量为 weights[i]
, 价值为 values[i]
. 这个题目中的物品不可以分割, 要么装进包里, 要么不装, 不能说切成两块装一半
, 这就是 0-1
背包的来历. 如以下示例, 最优是可以装载前两个物品, 它的总价值为 6
.
首先明确状态跟选择, 显然状态是重量