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

题目链接：
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;
 }