HDU1114 Piggy-Bank

2017年8月12日

有个储存罐,没硬币时重量为e,有硬币时重量为f,另给出n个硬币的质量和分值,求这个储存罐最少装有多少钱?

因为一个储存罐中可以装很多相同的硬币,因此可以判断这是道完全背包.而又必须在完全装满的条件下求最小值,初始化为 inf,然后求最小值,如果结果是 inf,输出 “This is impossible.”

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1114

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 505;
const int M = 10005;
int p[N], w[N], dp[M];
int main()
{
    int tt;
    scanf("%d", &tt);
    while (tt--) {
        memset(dp, inf, sizeof(dp));
        int e, f, n, d;
        scanf("%d%d%d", &e, &f, &n);
        d =  f - e;
        for (int i = 1; i <= n; i++)
            scanf("%d %d", p + i, w + i);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = w[i]; j <= d; j++) {
                dp[j] = min(dp[j], dp[j - w[i]] + p[i]);
            }
        }
        if (dp[d] == inf) {
            printf("This is impossible.\n");
        } else {
            printf("The minimum amount of money in the piggy-bank is %d.\n", dp[d]);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注