北航算法第三次练习赛- DP大作战—组合背包 | Eternal_zttz

北航算法第三次练习赛- DP大作战—组合背包

致敬DP

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
#include <cstdio>
#include <algorithm>
#include <algorithm>
using namespace std;

#define M 1000010
#define N 1000
int v[N],w[N],c[N],f[M],x;

void zero(int weight,int value){
for (int j = x;j>=weight;j--)
f[j] = max(f[j],f[j-weight]+value);
}

void complete(int weight,int value){
for (int j = weight;j<=x;j++)
f[j] = max(f[j],f[j-weight]+value);
}

void mutil(int weight,int value,int count){
int k;
if(weight*count >=x){
complete(weight, value);
return;
}
k = 1;
while(k<count){
zero(k*weight, k*value);
count -= k ;
k*=2;
}
zero(weight*count, value*count);
}

int main(){
int n,num;
scanf("%d",&n);
while(n --){
scanf("%d %d",&x,&num);
for (int i = 0;i<num;i++)
scanf("%d %d %d",&v[i],&w[i],&c[i]);
for (int k = 0;k<num;k++){
if(c[k] == 233) complete(w[k], v[k]);
else mutil(w[k], v[k], c[k]);
}
printf("%d\n",f[x]);
}
return 0;
}
-------------The End-------------