题目描述

给定N种硬币，其中第 i 种硬币的面值为Ai,共有Ci个。

从中选出若干个硬币，把面值相加，若结果为S，则称“面值S能被拼成”。

求1~M之间能被拼成的面值有多少个。

输入格式

输入包含多组测试用例。

每组测试用例第一行包含两个整数N和M。

第二行包含2N个整数，分别表示A1,A2,…,AN和C1,C2,…,CN。

当输入用例N=0，M=0时，表示输入终止，且该用例无需处理。

输出格式

每组用例输出一个结果，每个结果占一行。

数据范围

1≤N≤100,
1≤M≤105,
1≤Ai≤105,
1≤Ci≤1000

输入样例

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

输出样例

8
4

模型

多重背包模型

思路

由于是背包模型，所以我们可以采用动态规划来解决这个问题
那么就首先就需要分析怎么得到状态表示和状态计算。

状态表示

f[j](bool) 表示在i阶段中能否拼出面值为j的情况；
由于本题仅关注“可行性”(面值是否能拼成)而非“最优性”所以根据动态规划的过程我们可以发现，若前i种硬币能拼成面值j，那么只有两种可能的情况

1

前i-1种硬币就能拼成面值j，即在第i阶段开始前，f[j]已经成为true。

2

使用了第i种硬币，即在第i阶段的递推过程中，发现f[j-a[i]]为true，从而使用一个i硬币，使f[j]变为true。

于是可以考虑一种贪心策略：设used[j]表示在第i阶段下将f[j]变为true至少需要使用多少枚第i种硬币。

为了满足我们的贪心策略，我们应该尽量多的使用第1种情况,也就是说在f[j-a[i]]为true时，若f[j]已经为true，就不进行DP转移,并令used[j]=0(我们并没有使用第i种硬币)仅当f[j-a[i]]为true而f[j]为false且已经使用的i硬币used[j-a[i]]<c[i]时，我们使用一个i硬币使f[j]变为true，used[j]=used[j-a[i]]+1;

算法(贪心加动态规划)

时间复杂度$O(N*M)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int C=1010,M=1e5+10,N=105;

int n,m;
int a[N];
int c[C];
bool f[M];

int main()
{
    while(scanf("%d%d",&n,&m),n||m)
    {
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) scanf("%d",&c[i]);

        memset(f,0,sizeof f);
        f[0]=1;
        int used[M];
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=m;j++) used[j]=0;

            for(int j=a[i];j<=m;j++)
                if(!f[j]&&f[j-a[i]]&&used[j-a[i]]<c[i])
                    f[j]=1,used[j]=used[j-a[i]]+1;
        }

        int ans=0;
        for(int i=1;i<=m;i++)
            if(f[i]) ans++;
        printf("%d\n",ans);    
    }

    return 0;
}