poj1742 动态规划经典多重背包

梦里梦外; 2022-08-03 08:22 213阅读 0赞

有n种不同面值的硬币，面值各为A1,A2,A3。。AN，数量各为C1,C2,C3,,,,,CN。给定数m，问这些硬币能组成小于等于m的数中的哪些数，输出这些数的数目。

开始想的是从1到m判断每个数是不是能被这些硬币组成，但是判断每个硬币的数量的时候出现了问题，难以统计每种硬币使用的数目，

后来去网上搜了搜，发现可以以每种硬币为开始，把每种硬币能组成的数记录下来，这样在统计每种硬币数目的时候就好统计了。借鉴了别人的思路。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    int value[110];
    int num[110];
    int cnt[100010];
    bool dp[100010];
    
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m) && n)
        {
            mem(dp,0);
            for(int i=1;i<=n;i++)
            {
                value[i]=in();
            }
            for(int i=1;i<=n;i++)
            {
                num[i]=in();
            }
            int ans=0;
            dp[0]=1;
            for(int i=1;i<=n;i++)
            {
                mem(cnt,0);//换一种硬币之后cnt数组清零
                for(int j=value[i];j<=m;j++) //从当前硬币开始看它能组成哪些数
                {
                    if(!dp[j] && dp[j-value[i]] && cnt[j-value[i]]<num[i])//没有被组成的，并且使用当前硬币能组成的，并且当前硬币数目还够的情况下
                    {
                        ans++;
                        dp[j]=1;
                        cnt[j]=cnt[j-value[i]]+1;  //记录当前硬币的使用情况
                    }
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }