傳送門：
Coins
題意：
N 個錢幣，面額 A1 A2 … An 的錢幣分別有 C1 C2 … Cn 個。
能湊出 [1, M] 中的值多少個。
1 <= N <= 100
M <= 100000
1 <= Ai <= 100000
1 <= Ci <= 1000
思路：
多重背包問題。
code:
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
#include <iostream>
#include <cstring>
using namespace std;
int M,N,ans, dp[100005], arr[101][2] ;
void init(){
memset(dp, -1, sizeof(dp));
ans = dp[0] = 0;
}
int main(){
while(scanf("%d %d", &N, &M)==2 && (N+M)){
init();
for(int i=0;i<N;i++)
scanf("%d", &(arr[i][0]));
for(int i=0;i<N;i++)
scanf("%d", &(arr[i][1]));
for(int i=0;i<N;i++)for(int j=0;j<=M;j++){
if(dp[j]>=0) dp[j] = arr[i][1];
else if(j<arr[i][0] || dp[j-arr[i][0]]<1)
dp[j] = -1;
else dp[j] = dp[j-arr[i][0]] -1;
}
for(int i=1;i<=M;i++)if(dp[i]>=0)ans++;
printf("%d\n",ans);
}
}