背包问题-动态规划
概念
背包问题是一类组合优化问题，抽象定义：
有一系列的物品，每样都有重量和价值，选择一些物品使得总的重量不超过限制，总的价值尽可能大。
背包是一种隐喻，即假设某人有固定容量的背包，怎样选择物品，使得物品的总价值最高。
应用
- 投资组合选择
- 原料最优化切割
- Merkle–Hellman 密钥的生成
1999年的一项研究表明，在组合优化工程领域的75个问题中，背包问题是处在第19位，排在后缀树和装箱问题之后。
定义
01背包问题
有界背包问题
无界背包问题
一个01背包问题
分割等和子集
参考
https://en.wikipedia.org/wiki/Knapsack_problem
https://tangshusen.me/2019/11/24/knapsack-problem/
https://www.cnblogs.com/DAYceng/p/17301118.html
https://zh.wikipedia.org/wiki/动态规划