【动态规划】背包 DP 学习笔记

背包问题是一类经典的可以使用动态规划解决的问题。先看以下几个动态规划基本模型：

0/1 背包问题

0/1 背包问题基本模型是：给定 $n$ 个物品，每个物品有一个价值和一个体积，分别记作 $w_i$ 和 $v_i$，给定一个容量为 $m$ 的背包，把每个物品装入背包需要占用 $w_i$ 的体积，总占用体积不能超过背包容量，获得的价值是 $v_i$。求如何装入物品的所有方案中，价值和的最大值。

在这道例题中，我们具体研究此类背包问题的状态表示，状态计算与代码实现细节：洛谷 P1048 采药 - Solution

完全背包问题

完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。
在刚刚采药一题的题解中，我们写到，只要把 0-1 背包的空间优化后的代码中一个循环倒过来，就可以解决完全背包问题。
具体的原理和代码实现我们看这道例题：