题目描述
在ACM可以做任何事情之前,必须准备好预算并获得必要的财政支持。这项行动的主要收入来自不可逆约束货币(IBM)。这个想法很简单。每当某个acm队员有零钱时,他就会把所有的硬币都扔进一个存钱罐。你知道这个过程是不可逆的,不打碎存钱罐,硬币就不能取出。在足够长的时间之后,存钱罐里应该有足够的现金来支付所有需要支付的东西。
但是存钱罐有个大问题。无法确定里面有多少钱。所以我们可能把猪打碎,结果发现钱不够。显然,我们想避免这种不愉快的局面。唯一的可能是称一下存钱罐的重量,试着猜里面有多少硬币。假设我们能够准确地确定猪的重量,并且我们知道某一货币的所有硬币的重量。然后我们可以保证存钱罐里有一些最低数额的钱。你的任务是找出最坏的情况,并确定存钱罐内的最低现金数额,我们需要你的帮助。再也没有过早破碎的猪了!
输入
输入由 $T$ 个测试用例组成。$T$ 在输入文件的第一行给出。每个测试用例以包含两个整数 $e$ 和 $f$ 的行开始。它们表示空猪和装满硬币的猪的重量。两种方式均以克计。
任何猪的重量都不会超过 $10$ 公斤,即 $1 \leqslant e \leqslant f \leqslant 10000$。
在每个测试用例的第二行,有一个整数 $n\ (1 \leqslant n \leqslant 500)$,它给出了在给定货币中使用的各种硬币的数量。接下来是 $n$ 行,每行指定一种硬币类型。
这些行各包含两个整数,$p$ 和 $w \ (1 \leqslant p \leqslant 50000, \ 1 \leqslant w \leqslant 10000)$。$p$ 是硬币的货币单位,$w$ 是它的重量,单位为克。
输出
为每个测试用例只打印一行输出。该行必须包含“存钱罐中的最小金额 $x$”这句话,其中 $x$ 是使用给定总重量的硬币可以获得的最小金额。如果无法准确达到重量,请打印一行“这是不可能的”。
样例
输入:
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
输出:
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
算法
(完全背包) $O(tnm)$
本题为完全背包问题每种货币的数量没有限制。
求解重量为 $f - e$ 的情况下,放入存钱罐的最小值。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
template<typename T1, typename T2> bool chmin(T1& a, const T2& b) { if (a > b) { a = b; return 1; } return 0; }
const int N = 510, M = 10010;
const int INF = 0x3f3f3f3f;
int n, m;
int v[N], w[N]; // v[i] 表示第 i 种硬币的面值,w[i] 表示第 i 种硬币的重量
int dp[M]; // dp[j] 表示放入重量为 j 的存钱罐面值之和的最小值
int main() {
int t;
cin >> t;
while (t--) {
int e, f;
cin >> e >> f;
m = f - e;
cin >> n;
rep(i, n) cin >> v[i] >> w[i];
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
rep(i, n) {
for (int j = w[i]; j <= m; ++j)
chmin(dp[j], dp[j - w[i]] + v[i]);
}
if (dp[m] < INF) {
cout << "The minimum amount of money in the piggy-bank is " << dp[m] << ".\n";
}
else {
puts("This is impossible.");
}
}
return 0;
}