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函數，所以此題解了就。