最简单的背包是01背包和完全背包
01背包
P1048
形式化题意：有 n 物品，每个物品都有两个属性， w_i 和 c_i ，其中 w_i 是体积 c_i 是价值，求体积不能超过背包容量 v 的情况下，总价值最多是多少。
1. 定义状态： dp_{i,j} 表示对于前 i 个物品，背包容量为 j 时最大的价值。
2. 初始化： dp_{0,j}=0 ，因为没有物品可选价值为0。
3. 状态转移方程：我们发现每个物品有选和不选，不选就要从 dp_{i-1,j} 转移过来，选要满足 j≥w_i 然后从 dp_{i-1,j-w_i} 转移过来，同时价值加上 c_i ，将两者取最大值即可。
4. 答案：很明显答案是 dp_{n,v} 。
核心代码
for(int i=1;i<=n;++i)
for(int j=0;j<=v;++j)
if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
else dp[i][j]=dp[i-1][j];
cout<<dp[n][v];
01背包优化
我们发现我们发现每次转移只和 i-1 有关，那么我们可以压缩成一维，但是这样一个物品会被选多次，我们只要倒序枚举 j 就可以只选一次了。
核心代码如下
for(int i=1;i<=n;++i)
for(int j=v;j>=w[i];--j) dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
cout<<dp[v];
完全背包
P1616
形式化题意：有 n 每种物品，每种物品都有无限个，每种物品都有两个属性， w_i 和 c_i ，其中 w_i 是体积 c_i 是价值，求体积不能超过背包容量 v 的情况下，总价值最多是多少。
我们刚刚说01背包优化时，讲到正序枚举会选多次，这个刚好可以用在完全背包上，其他和01背包相同。
核心代码如下
for(int i=1;i<=n;++i)
for(int j=w[i];j<=v;++j) dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
cout<<dp[v];