背包问题:
给定限定范围,求子集不同组合的最优解
此问题是经典的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];}
};