n种硬币,每个硬币的值ai,有ci个,求能组成多少个不大于m的不同的金额。

思路

典型的多重背包

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int MAXN = 100005;
const int MAXM = 105;

int dp[MAXN]; //表示当前价值是否可以达到(0不可达,1可达)
int a[MAXM]; //value
int c[MAXM]; //num
int cnt[MAXN]; //表示达到j状态i物品的使用次数

int main(){
int n, m;
while(scanf("%d%d",&n,&m)!=EOF){
if(n==0 && m==0) //m可能为负数
break;
int ans = 0;
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 0; i < n; i++)
scanf("%d", a + i);
for (int i = 0; i < n; i++)
scanf("%d", c + i);
for (int i = 0; i < n; i++){
memset(cnt, 0, sizeof(cnt));
for (int j = a[i]; j <= m; j++){
if(dp[j-a[i]]==1 && dp[j]==0 && cnt[j-a[i]]<c[i]){
cnt[j] = cnt[j - a[i]] + 1;
dp[j] = 1;
ans++;
}
}
}
printf("%d\n", ans);
}
return 0;
}