hdu 2844 多重背包模板题 01背包、完全背包、多重背包模板

1
2
<p><span style="font-family: Arial, Helvetica, sans-serif;">分析：将多重背包转化为01背包思想，优化复杂度为O（Vsum（logM））；</span></p><p></p><p>AC代码：</p>

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>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[100005],c[105],v[105];
int m;
void CompletePack(int c,int w)
{
int i;
for(i=c;i<=m;i++)
dp[i]=max(dp[i],dp[i-c]+w);
}
void ZeroOnePack(int c,int w)
{
int i;
for(i=m;i>=c;i--)
dp[i]=max(dp[i],dp[i-c]+w);
}
void MultiplePack(int c,int w,int amount)
{
if(c*amount>=m)
{
CompletePack(c,w);
return;
}
int k;
k=1;
while(k<amount)
{
ZeroOnePack(k*c,k*w);
amount=amount-k;
k=2*k;
}
ZeroOnePack(c*amount,w*amount);
}
int main()
{
int n;
int flag[100005];
while(~scanf("%d%d",&n,&m)&&(n||m))
{
int i;
memset(dp,0,sizeof(dp));
memset(flag,0,sizeof(flag));
for(i=1;i<=n;i++) scanf("%d",&v[i]);
for(i=1;i<=n;i++) scanf("%d",&c[i]);
for(i=1;i<=n;i++)
{
MultiplePack(v[i],v[i],c[i]);
}
int ans=0;
for(i=1;i<=m;i++)
if(dp[i]) flag[dp[i]]=1;
for(i=1;i<=m;i++)
if(flag[i]) ans++;
printf("%dn",ans);
}
return 0;
}