1.最优子结构性质：最优解包含了其子问题的最优解，不是合并所有子问题的解，而是找最优的一条解线路，选择部分子最优解来达到最终的最优解。
2.子问题重叠性质：先计算子问题的解，再由子问题的解去构造问题的解（由于子问题存在重叠，把子问题解记录下来为下一步使用，这样就直接可以从备忘录中读取）。其中备忘录中先记录初始状态。
01背包与完全背包的比较：
在0/1背包问题中，第 i 件物品只可以放0个或者1个，即选择或者不选。而在完全背包问题中，第 i 件物品可以放入0，1，2…个。即每件物品可以放入无限多次。
与0/1背包相同的是，最大价值是物品数量 i 与背包容量 j 的函数。最终的最大价值就是物品数量 i 从0增长到n，背包容量 j 从0增长到m时的 f [ n ] [ m ] 函数值。f[ i ][ j ]表示前 i 件物品放入容量为 j 的背包的最大价值。
Original: https://www.cnblogs.com/star-tears/p/15634591.html
Author: Star_tears
Title: 背包
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/572424/
转载文章受原作者版权保护。转载请注明原作者出处！