全部用来买书,画重点,不能剩下钱!如果在这个场景下不好理解,可以尝试理解一下此题的另外一种问法:
现在有\(100\)元钱,需要换成零钱,那么有四种货币,问共有多少种对换方案?很显然是要求用完的,不能说换完了是\(98\)元,谁换零钱也不能赔是吧。
阅读上面的优化思路后,再来看下面的推导过程:
观察 \(f(i,j)\) 的 状态转移方程 进行变形
\(f(i,j) =f(i−1,j)+f(i−1,j−v_i)+⋯+f(i−1,j−sv_i)\)
\(f(i,j-v_i)=f(i−1,j−v_i)+⋯+f(i−1,j−sv_i)\)
由上述两个等式可以获得如下递推式:
\(f(i,j)=f(i−1,j)+f(i,j−vi)\)
- 这里不是取\(max\),而是计数方案,所以一直在加。
- 由于不是记录价值,所以没有\(w_i\)
把这个等式作为 状态转移方程 ,就可以把时间复杂度优化到 \(O(n×m)\)
同时,观察到该 转移方程 对于第 \(i\) 阶段的状态,只会使用第 \(i-1\) 层和第 \(i\) 层的状态
因此我们也可以采用 \(01\)背包 的 空间优化方案
时间复杂度:\(O(n×m)\)
空间复杂度:\(O(m)\)
一、朴素(原始TLE)版本
#include <bits/stdc++.h>
using namespace std;
const int N = 5;
const int M = 1010;
int n = 4; //四种物品
int v[N] = {0, 10, 20, 50, 100};//每种货币,下标从1开始
int m; //钱数
int f[N][M];//前i种物品,体积恰好是j的情况下的最大值
//完全背包
int main() {
cin >> m;
//base case
//前0种物品,体积是0的情况下只有一种方案
f[0][0] = 1;
for (int i = 1; i <= n; i++) //每个物品
for (int j = 0; j <= m; j++) //每个体积
for (int k = 0; v[i] * k <= j; k++) //个数
f[i][j] += f[i - 1][j - v[i] * k];
//输出
cout << f[n][m] << endl;
return 0;
}
二、二维优化后解法
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[5] = {0, 10, 20, 50, 100};
int f[5][N];
int main() {
int m;
cin >> m;
//base case
f[0][0] = 1;
for (int i = 1; i <= 4; i++)
for (int j = 0; j <= m; j++) {
//可以第i个物品选择0个,所以f[i][j]=f[i-1][j]
f[i][j] = f[i - 1][j];
//类似于前缀和的思想,利用前面的最优化方案数,
//再考虑增多空间情况下的数量,不断的递增过来,就是最多的方案数
if (v[i] <= j)f[i][j] += f[i][j - v[i]];
}
//一个整数,代表选择方案种数
printf("%d", f[4][m]);
return 0;
}
三、一维空间优化解法
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[5] = {0, 10, 20, 50, 100};
int f[N];
int main() {
int m;
cin >> m;
//base case
f[0] = 1;
for (int i = 1; i <= 4; i++)
for (int j = v[i]; j <= m; j++)
f[j] += f[j - v[i]];
//一个整数,代表选择方案种数
printf("%d", f[m]);
return 0;
}