＜ 背包问题 ＞
背包问题：
给定限定范围，求子集不同组合的最优解
此问题是经典的dp问题，如果用暴力/dfs去解几乎不会在限定时间内通过，动态规划是递归的性能优化，都是用来求解给定数据所有可能的方案 / 找到最优解
背包问题的细化有经典的两种：
01背包：给定背包容量V，每个物品都有体积v[i]，价格w[i]，问，每个物品最多只能取1次，怎样选取物品才能获得最高价值
完全背包：给定背包容量V，每个物品都有体积v[i]，价格w[i]，问，每个物品可以取无限次，怎样选取物品才能获得最高价值
01背包：
一个物品要么取（1次），要么不取（0次）
当背包容量为j，有i种物品时，可以选取的最高价值 == max（取：此物品价值 + （背包容量 - 此物品体积）的最高价值 ，不取：不考虑此物品的最高价值）
状态转移方程：f[i][j] = max(f[i-1][j-v[i]]+w[i], f[i-1][j])
伪代码：
for i < -1 to N//遍历每个商品for j < -1 to W ://列表示价格if j < w[i] ://如果背包容量 >物品容量，则商品无法放入背包result[i][j] = result[i - 1][j]else :result[i][j] = max(result[i - 1][j], v[i] + result[i - 1][j - w[i]])
return result完全背包：
每个物品可以取k次（0 --- (j / v[i]) )
当背包容量为j，有i种物品时，可以选取的最高价值 == max（取(k= 0, 1, 2, 3, 4,...) 次：此物品价值 + （背包容量 - 此物品体积）的最高价值 ）
状态转移方程：f[i][j] = max(k= 0, 1, 2, 3, 4,...j / v-i]) (f[i-1][j- k * v[i]] + k * w[i] )
实例：
面试题 08.11. 硬币 ：给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法
状态转移方程：f(i,v) =（j=0--k）∑ f(i−1,v− j×ci)
这里没有用max是因为并非找最优解，而是找所有可行解的数量（也就是 +=）
代码：
class Solution {
private:static constexpr int mod = 1000000007;static constexpr int coins[5] = {0, 25, 10, 5,1};//这里取0位，填充第0行int ans[5][1000005];
public:int waysToChange(int n) {for (int i = 0; i <= 4; i++) //这里从0开始，填充第0列ans[i][0] = 1;for (int i = 1; i <= 4; i++) {for (int j = 1; j <= n; j++) {for (int k = 0; k * coins[i] <= j; k++) {ans[i][j] += ans[i - 1][j - k * coins[i]] % mod;}}}return ans[4][n];}
};可是上述还是超时，因此需要优化为一维dp
把求和式展开书写：f(i,v)=f(i−1,v)+f(i−1,v−ci)+f(i−1,v−2ci)⋯f(i−1,v−kci)
那么我们可以得到使用 v−ci 替换 v:f(i,v−ci)= f(i−1,v−ci)+f(i−1,v−2ci) +f(i−1,v−3ci)⋯f(i−1,v−kci)
上面可以合并简化：f(i,v)=f(i−1,v)+f(i,v−ci)
因此这就是一维dp的状态转移方程，因此不必考虑k了
class Solution {
private:static constexpr int mod = 1000000007;static constexpr int coins[4] = {25, 10, 5, 1};public:int waysToChange(int n) {vector<int> f(n + 1);f[0] = 1;for (int c = 0; c < 4; ++c) {int coin = coins[c];for (int i = coin; i <= n; ++i) {f[i] = (f[i] + f[i - coin]) % mod;}}return f[n];}
};