K - Coins(多重背包的变种题）

亦凉 2022-02-23 03:26 215阅读 0赞

### 题目描述： ###

Whuacmers use coins.They have coins of value A1,A2,A3…An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn’t know the exact price of the watch.  
You are to write a program which reads n,m,A1,A2,A3…An and C1,C2,C3…Cn corresponding to the number of Tony’s coins of value A1,A2,A3…An then calculate how many prices(form 1 to m) Tony can pay use these coins.  
Input  
The input contains several test cases. The first line of each test case contains two integers n(1 ≤ n ≤ 100),m(m ≤ 100000).The second line contains 2n integers, denoting A1,A2,A3…An,C1,C2,C3…Cn (1 ≤ Ai ≤ 100000,1 ≤ Ci ≤ 1000). The last test case is followed by two zeros.  
Output  
For each test case output the answer on a single line.  
Sample Input  
3 10  
1 2 4 2 1 1  
2 5  
1 4 2 1  
0 0  
Sample Output  
8  
4  
题意：  
第一行 输入n（表硬币种类） 和 m  
第二行前n个数表示每种硬币价值，后n个数表示每种硬币数量。  
问，能用这些硬币表示出多少个m以内的价值。

##### 分析： #####

这是一个典型的dp背包求方法数。  
不过，我们可以换种思路。 就是把硬币能表示出来的价值都标记一下。然后最后一个循环计算有多少个价值是被标记过了的。

这样的话，我们就只需要用一个dp将所有有可能的价值都表示出来。 ‘  
同时本题，我们用二进制优化。  
代码：

#include"string.h"
    #include"functional"
    #include"iostream"
    #include"vector"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    #define scanll(a,b) scanf("%I64d%I64d",&a,&b);
    #define scanl(a) scanf("%I64d",&a);
    #define scanff(a,b) scanf("%lf%lf",&a,&b);
    #define scan1f(a) scanf("%lf",&a);
    #define prinll(a,b) printf("%I64d %I64d",a,b);
    #define prinl(a) printf("%I64d",a);
    #define printff(a,b) printf("%lf %lf",a,b);
    #define printlf(a) printf("%lf",a);
    #define OK printf("\n");
    #define MAXSIXE 10010
    #define INF 1000101010
    struct Good
    {
        ll p;
    };
    ll dp[100010];
    int main()
    {
        ll n,m;
        while(~scanf("%lld%lld",&n,&m),n+m)
        {
            vector< Good > goods;
            ll p[110],c[110];
            for(ll j = 0; j <= m; j ++)//将所有的初始值为-INF，这样才不会影响结果。 
                dp[j] = -INF;
            dp[0] = 0;//边界值为0
            for(ll i = 1; i <= n; i ++)
                scanl(p[i]);
            for(ll i = 1; i <= n; i ++)//二进制优化
            {
                scanl(c[i]);
                for(ll j = 1; j <= c[i]; j <<= 1)
                {
                    goods.push_back({p[i] * j});
                    c[i] -= j;
                }
                if(c[i] > 0)
                    goods.push_back({ c[i] * p[i] });
            }
            //dp求价值
            for(ll i = 0; i < goods.size(); i ++)
            {
                for(ll j = m; j >= goods[i].p; j --)//01背包求解
                {
                    ll t;
                    t = max(dp[j],dp[j-goods[i].p] + goods[i].p);
                    dp[j] = t;
                }
            }
            ll sum = 0;
            for(ll j = 1; j<= m; j++)
                if(dp[j] > 0)
                    sum ++;
            printf("%lld\n",sum);
        }
    }

参考博客：[https://blog.csdn.net/sdjzping/article/details/8619405][https_blog.csdn.net_sdjzping_article_details_8619405]  
[https://blog.csdn.net/vvmame/article/details/76697198][https_blog.csdn.net_vvmame_article_details_76697198]

[https_blog.csdn.net_sdjzping_article_details_8619405]: https://blog.csdn.net/sdjzping/article/details/8619405
[https_blog.csdn.net_vvmame_article_details_76697198]: https://blog.csdn.net/vvmame/article/details/76697198