DP
1. 理论
- 每个大问题的子问题都是最优的，所以才可以直接记录下来
- 在下次寻找子问题的最优解时，直接使用
与分治算法不同的是：
- 适合 dp 请求的问题，经分解得到的子问题往往不是互相独立的
- 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步求解
2. 最优子结构
原问题的最优解包含子问题的最优解
3. 状态转移方程
- 写状态转移方程的程序，一般以递推的方式实现
- 虽然时间复杂度和记忆化搜索一样
- 而且在循环中会计算一些无意义的节点
- 但是递推免去了调用时进栈出栈的操作，而且避免了在递归时层数过多时栈溢出的情况
\(f(i,j)=max\left \{ f(i-1,j) ,f(i-1,j-w(i))+v(i)\right \}\)
4. 手办问题
| 手办名 | 价格 | 喜欢程度 |
|---|---|---|
| 兵长 | 10 | 24 |
| 蕾姆 | 4 | 9 |
| 小埋 | 4 | 9 |
| 和泉纱雾 | 5 | 10 |
| 空条承太郎 | 3 | 2 |
你现在 有 13 元
4.1 贪心算法
- 算出每个物品的性价比
- 优先买性价比高的物品
| 手办名 | 价格 | 喜欢程度 | 性价比 |
|---|---|---|---|
| 兵长 | 10 | 24 | 2.4 |
| 蕾姆 | 4 | 9 | 2.25 |
| 小埋 | 4 | 9 | 2.25 |
| 和泉纱雾 | 5 | 10 | 2 |
| 空条承太郎 | 3 | 2 | 0.67 |
最终的喜欢程度为：24 + 2 = 26
4.2 0-1 背包问题
| 背包问题 | 说明 |
|---|---|
| 0-1 背包 | 每个物品最多一个 |
| 完全背包 ==> 可以转化成 0-1 背包 | 每种物品无限件 |
| 手办是一个整体 |
- 你不能只买?和大腿，按照比例给钱，所以不能用贪心来解决
普通递归实现
# f(i, j)：当还剩 j 元钱时，前 i 个物品能达到的最大喜欢值
# max【不买这个商品的价值，买这个商品的价值】