ACdream 1110 True love （多重背包+dp）

﹏ヽ暗。殇╰゛Y 2022-06-12 12:19 123阅读 0赞

题目链接：  
[ACdream 1110][]

题意：  
给你一些物品的体积和对应的数量，求可以拿走多少种总体积不一样的物品，且不超过背包的容量。

题解：  
多重背包呗。  
dp  题。

设 dp\[i\]  表示容量为 i  的背包。  
那么容易得到转移方程：  
dp\[j\+a\[i\]\]>=dp\[j\]\+1  时：  
dp\[j\+a\[i\]\]=dp\[j\]\+1  且 j\+a\[i\]<=cap

最后再统计一遍就可以了。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 100010;
    int n,cap;
    int a[maxn],b[maxn];
    int dp[maxn];
    
    int main()
    {
        int t ;
        scanf("%d",&t);
        for(int i =1;i<=t;i++)
        {
            printf("Case %d: ",i);
            scanf("%d%d",&n,&cap); 
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&b[i]);
            }
            for(int i=1;i<=cap;i++){
                dp[i] = -1;
            }
            dp[0] = 0;
    
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=cap;j++)
                {
                    if(dp[j]!=-1){
                        dp[j] = 0;
                    }
                }
                for(int j = 0;j <= cap;j++)     
                {
                    if(dp[j] == -1)continue;
                    if(dp[j] > b[i])
                    {
                        dp[j] = -1;continue;
                    }
                    if(j + a[i] <= cap && (dp[ j + a[i] ] == -1 || dp[ j + a[i] ] >= dp[j] + 1))
                    {
                        dp[j+a[i]] = dp[j] + 1; 
                    }  
                }
            }
            int ans = 0;
            for(int i=1;i<=cap;i++)
            {
            //  cout<<"dp["<<i<<"]="<<dp[i]<<endl;
                if(dp[i] != -1)
                {
                    ans ++;
                }
            }
            cout<<ans<<endl;
    
        }
        return 0;
     }

[ACdream 1110]: http://acdream.info/problem?pid=1110