背包问题(Python)

Reference

• 背包九讲实例：01背包问题
• 知乎什么是动态规划 (推荐看这个) https://www.zhihu.com/question/23995189

暴力解动态规划Brute Force

贪心&动态规划

贪心：即每一次选择都选择当前状态下的最优

动态规划：将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

• 最优子结构：大问题的最优解可以由小问题的最优解推出
• 在可能解的空间寻找最优
• 自带减枝

顺序递推&记忆化

0-1背包

分数背包