背包问题-动态规划

概念

背包问题是一类组合优化问题，抽象定义：
有一系列的物品，每样都有重量和价值，选择一些物品使得总的重量不超过限制，总的价值尽可能大。

背包是一种隐喻，即假设某人有固定容量的背包，怎样选择物品，使得物品的总价值最高。

应用

1. 投资组合选择
2. 原料最优化切割
3. 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/动态规划