url: https://www.luogu.com.cn/problem/P2851
tag:
动态规划，背包DP，进制，USACO，2006
思路：
可以用背包来做。用 f[i] 表示john付i块钱时最少的硬币数，用 g[i] 表示店主找零i块钱时最少的硬币数，对于f来说，因为硬币数量有限所以需要用多重背包来完成。而对于g来说因为硬币无限多，所以可以用完全背包。对于体积上限取多少可以参考： https://www.luogu.com.cn/article/sd0bx6un
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 10010, M = 150;
int c[M], v[M];
int f[N + M * M], g[N + M * M];
int n, t, mx, sum;
int main()
{
cin >> n >> t;
for (int i = 1; i <= n; i ++)
{
cin >> v[i];
mx = max(mx, v[i] * v[i]);
}
for (int i = 1; i <= n; i ++)
{
cin >> c[i];
sum += v[i] * c[i];
}
if (sum < t)
{
cout << -1 << endl;
return 0;
}
memset(f, 0x3f, sizeof f);
memset(g, 0x3f, sizeof g);
g[0] = 0;
f[0] = 0;
for (int i = 1; i <= n; i ++)
for (int j = v[i]; j <= mx; j ++)
g[j] = min(g[j], g[j - v[i]] + 1);
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= c[i]; j *= 2)
{
for (int k = mx + t; k >= j * v[i]; k --)
f[k] = min(f[k], f[k - j * v[i]] + j);
c[i] -= j;
}
if (c[i])
for (int k = mx + t; k >= c[i] * v[i]; k --)
f[k] = min(f[k], f[k - c[i] * v[i]] + c[i]);
}
int res = 0x3f3f3f3f;
for (int i = t; i <= t + mx; i ++)
res = min(res, f[i] + g[i - t]);
cout << (res == 0x3f3f3f3f ? -1 : res) << endl;
return 0;
}