算法:背包问题 DP
时间复杂度: $O(100000000)$
一开始以为用 $dfs$ 做的,后来发现爆栈了。
一看,原来是完全背包问题,主要还是对各种类型的背包问题十分的不熟。
将凑出的的 面值 当作 体积,而邮票的 张数 当作 价值,问题就转化为求解该体积下价值的最小值,依据数据范围,体积最大可达 $10000 \times 200 = 2000000$。
$f[i]$ 表示 $i$ 体积下所需邮票张数的最小值,而 $f[x] \le k$ 的 $x$ 的最大值 即为本题的答案。
注意本题初始化为 $INF$ 及 $f[0] = 0$。
相关例题
上述三题分别是 01 背包问题求总方案数、完全背包问题求总方案数 和 完全背包问题(裸),放在一起主要是能够进行比较,本题求解的价值的最小值,也算是完全背包问题的一种变形。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2000010;
int n, k, m = N - 1;
int f[N];
int main()
{
cin >> k >> n;
memset(f, 0x3f, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; ++i) {
int v;
cin >> v;
for (int j = v; j <= m; ++j) {
f[j] = min(f[j], f[j - v] + 1);
}
}
int x = 0;
while (f[x] <= k) ++x; // 凑不出来或者凑出来邮票的张数大于 k
cout << x - 1 << endl;
return 0;
}