转自：https://blog.csdn.net/yandaoqiusheng/article/details/84782655/，背包九讲
有背包容量为V，N个物品，每个重量为w[i]，价值为v[i]，每个物品仅有一件，要使得背包价值最大怎么装物品？
定义dp数组含义：dp[i][j]表示考虑前i个物品在背包容量恰为j的情况下达到的最大价值。
状态转移方程：
f[i][j]=max(f[i?1][j],f[i?1][j?w[i]]+v[i])
解释：针对第i个物品有两种选择，一是放进背包，一是不放进背包。max中的第一项就是不放进背包，那么就转换为考虑前i-1件物品放进容量为j的背包；第二项是放进背包，问题转化为前i-1件物品放入容量为j-w[i]的背包，此时的最大价值是再加上当前的物品的价值。
使用滚动数组的思想：
?for (int i = 1; i <= n; i++)//遍历物品 for (int j = V; j >= 0; j--)//遍历容量 f[j] = max(f[j], f[j - w[i]] + v[i]);
外层遍历物品，内层要从大到小遍历，因为物品最多只能取一次。（完全背包问题中是从小到大遍历容量，因为可以取无限次。）
只要数量有限制都只能从大到小遍历，其实从原始公式中看的更明显，从大到小只保证使用的是i-1的计算结果。
力扣例题：416. 分割等和子集
有背包容量为V，N个物品，每个重量为w[i]，价值为v[i]，每个物品有无数件，要使得背包价值最大怎么装物品？
dp数组含义和上面相同，按照每个物品可取数量可以这么写，
f[i][j]=max(f[i?1][j?k?w[i]]+k?v[i])∣0<=k?w[i]<=j
但是不好解。
for (int i = 1; i <= n; i++)//遍历物品 for (int j = w[i]; j <= V; j++)//遍历容量 f[j] = max(f[j], f[j - w[i]] + v[i]);
遍历物品，但背包容量是从小到大的，因为物品可以无限次使用。
两层for循环可以替换？
举例：322. 零钱兑换
for(int i=1;i<=amount;i++){//容量在外，每次开始一次都表示之前的容量已确定最终的结果 for(int j=0;j<coins.size();j++){ if(coins[j]>i)continue; dp[i]=min(dp[i],dp[i-coins[j]]+1); } } for(int i=0;i<coins.size();i++){//硬币在外，每次都用一个硬币更新所有的容量一次 for(int j=coins[i];j<=amount;j++){ dp[j]=min(dp[j],dp[j-coins[i]]+1); } }
每件物品多了个数量限制。
//还没有做过这样得的题目。
有的可以取0-1次，有的可以取无限次，有的能取k次。
那么针对0-1和完全可以分开求解：
p[i]:每个物品的件数，0代表无穷个 for (int i = 1; i <= n; i++)//遍历物品 if (p[i] == 0)//完全背包问题 for (int j = w[i]; j <= V; j++)//从小到大遍历 f[j] = max(f[j], f[j - w[i]] + v[i]); else for (int k = 1; k <= p[i]; k++)//如果p[i]是1，就是0-1背包问题，否则是多重背包问题 for (int j = V; j >= w[i]; j--) f[j] = max(f[j], f[j - w[i]] + v[i]);
//还没有做过这样的题目，希望做的时候能想到解法。
现在物品有两种重量，两种价值，当然也有两个背包，也就是有两个限制，那么就再多加一维状态：
定义dp数组含义：dp[i][j][k]表示考虑前i件物品，背包容量分别为j和k时能达到的最大价值。
状态转移：
max(f[i?1][j][k],f[i?1][j?w[i]][k?g[i]]+v[i])//不放、放
那么此时就需要从大到小遍历：
for (int i = 1; i <= n; i++) for (int j = V; j >= w[i]; j--)//两层均需要从大到小遍历 for (int k = T; k >= g[i]; k--) f[j][k] = max(f[j][k], f[j - w[i]][k - g[i]] + v[i]);
时间复杂度就是三层for循环乘积了，空间复杂度降成了二维。
题目：474. 一和零
原文：https://www.cnblogs.com/BlueBlueSea/p/14425638.html