Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 32768/32768 K
(Java/Others)
Total Submission(s): 6450 Accepted
Submission(s): 2628
|
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 |
#include <iostream>#include <cstdio>using
namespace std;#define N 100003int c[N],w[N];int dp[N];int n, v;void ZeroOnePack(int
cost,int
weight) //01背包{ for(int
k=v; k>=cost; k--) dp[k] = max(dp[k],dp[k-cost]+weight);}void
CompeletPack(int
cost,int
weight) //完全背包{ for(int
k=cost; k<=v; k++) dp[k] = max(dp[k],dp[k-cost]+weight);}void
MultiplePack(int
cost,int
weight,int
amount) //多重背包{ if(cost*amount>=v) { CompeletPack(cost,weight); return; } else { int
k=1; while(k<amount) { ZeroOnePack(k*cost,k*weight); amount = amount-k; k=k*2; } ZeroOnePack(amount*cost,amount*weight); }}int
main(){ int
i; while(scanf("%d %d",&n,&v) && n && v) { for(i=0; i<n; i++) scanf("%d",&c[i]); //金币面值 for(i=0; i<n; i++) scanf("%d",&w[i]); //每种金币的个数 memset(dp,0,sizeof(dp)); for
(i=0; i<n; i++) { MultiplePack(c[i],c[i],w[i]); } int
sum=0; //记录可以组成的金额数目 for(i=1; i<=v; i++) { if(dp[i]==i) sum++; } printf("%d\n",sum); } return
0;} |
原文：http://www.cnblogs.com/yazhou/p/3726265.html