HDU 1114 Piggy-Bank (完全背包)

我会带着你远行 2022-08-21 14:40 37阅读 0赞

题目链接：  
[http://acm.hdu.edu.cn/showproblem.php?pid=1114][http_acm.hdu.edu.cn_showproblem.php_pid_1114]

题目大意：  
有一个容量为F-E的储钱罐，给你n种不同的硬币，问在储钱罐装满的情况下，储钱罐里存储的钱最少是多少，如果不能正好存满，那么输出不可能。

解题思路：明显是一个完全背包，但是和原本的有些不同，这里的背包求的是最小容量，而且必须装满

既然是最小容量 那么dp的时候把max改成min就可以了  
如果要必须装满，我们就要背包只要有剩余的容量，背包非常的大，可以这样初始化

dp[0]=0; for(int i=1; i<=cap; i++) dp[i]=1e9;

当刚好能买到背包容量为0时则加上钱币价值  
否则如果有剩余的容量，且没有金币组合能满足这个容量时，它必然是  
1e9

举个例子：  
1 10  
3  
6 3  
3 2  
1 5

更新顺序

1 0 1 2 3 4 5 6 7 8 9  
2 0 inf inf inf inf inf inf inf inf inf  
3 0 inf inf 6 inf inf 12 inf inf 18  
4 0 inf 3 6 6 9 9 12 12 15  
5 0 inf 3 6 6 1 9 4 7 7

如果没有匹配到就是inf，只要能匹配，所以我们不会选到没有匹配的项

#include<iostream>
    #include<cstdio>
    using namespace std;
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int e,f,n,dp[10005],v[505],w[505];
            scanf("%d %d %d",&e,&f,&n);
    
            int cap=f-e;
            for(int i=0; i<n; i++) scanf("%d %d",&v[i],&w[i]);
    
            dp[0]=0;
            for(int i=1; i<=cap; i++)   dp[i]=1e9;
    
            for(int i=0; i<n; i++)
                for(int j=0; j<=cap; j++)
                    if(j>=w[i]) dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
    
            if(dp[cap]==1e9)   printf("This is impossible.\n");
            else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[cap]);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1114]: http://acm.hdu.edu.cn/showproblem.php?pid=1114