问题梗概
有一个承重有限的背包 有若干商品，价值和重量均不同，商品不能再细分 要求背包装入的商品总价值最高
详解
个人补充
- 对于状态的理解
- 直观来说, 都会认为有两个状态: 背包所剩空间, 供选择的物品
- 但第二个状态是一个集合, 难以量化, 这时候采用一个技巧: 转换为”按顺序”考虑的状态
- 顺序遍历n个物品, 遍历到某个物品的时候, 前面的物品已经决定好要选择哪些物品, 只需要考虑后面剩下物品就行了
- 则状态为剩下i个物品
- 空间优化
- 小技巧: 正序不行, 试试倒序, 变换思路
有一个承重有限的背包 有若干商品，价值和重量均不同，商品不能再细分 要求背包装入的商品总价值最高