【dp每日一题】HDU 1114 Piggy-Bank

大意：

给出储钱罐的罐重和总重，以及m种硬币的数量和面值，问符合条件（即硬币重量=总重-罐重）的硬币最小的面值和为多少

思路：

完全背包，容量为总重-罐重，价值为硬币的面值

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 5;
typedef long long LL;
int T, n, v, dp[N], m, s[N], vul[N];
int main() {
    cin >> T;
    while (T--) {
        int x, y;
        cin >> x >> y;
        v = y - x;
        cin >> m;
        for (int i = 0; i < m; i++) {
            cin >> vul[i] >> s[i];
        }
        memset(dp, 0x3f, sizeof dp);
        dp[0] = 0;
        for (int i = 0; i < m; i++) {
            for (int j = s[i]; j <= v; j ++) {
                dp[j] = min(dp[j], dp[j - s[i]] + vul[i]);
            }
        }
        if(dp[v]==0x3f3f3f3f){
            cout << "This is impossible." << endl;
        }
        else{
            cout << "The minimum amount of money in the piggy-bank is " << dp[v] << "." << endl;
        }
    }
    return 0;
}