view code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAX 210000000
int t, n, c[505], w[505], dp[10010], i, j, v, e, f;
int min(int a, int b)
{
if (a < b) return a;
else return b;
}
int main()
{
while (cin >> t)
{
while (t--)
{
cin >> e >> f;
v = f - e;
cin >> n;
for (i = 1; i <= n; i++)
cin >> w[i] >> c[i];
for (i = 0; i <= v; i++)
dp[i] = MAX;
dp[0] = 0;
for (i = 1; i <= n; i++)
for (j = c[i]; j <= v; j++)
dp[j] = min(dp[j], dp[j - c[i]] + w[i]);
if (dp[v] != MAX) cout << "The minimum amount of money in the piggy-bank is " << dp[v] << "." << endl;
else cout << "This is impossible." << endl;
}
}
return 0;
} 声明，此题是一个赤裸裸的完全背包，只是有一个问题我当时没处理掉，那就是……怎么判断到底放没放满，后来我释然了，因为如果把dp数组更新到最大值，如果没放满，dp[v]是更新不了的，尤其还是个min函数，所以此题解了就。