一位骨头收集者有一个体积为V的背包,不同的骨头有不同的价值和体积,现在考虑到每块骨头的价值及体积,计算出能收集的骨头最大的价值。

思路

0-1背包常规题

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


#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int MAXN = 1005;

int dp[MAXN];

struct node{
int a;
int b;
} bone[MAXN];

int main(){
int T;
scanf("%d", &T);
while(T--){
int N, V;
scanf("%d%d", &N, &V);
for (int i = 0; i < N; i++){
scanf("%d", &bone[i].a);
}
for (int i = 0; i < N; i++){
scanf("%d", &bone[i].b);
}
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; i++){
for (int j = V; j >= bone[i].b; j--){
dp[j] = max(dp[j], dp[j - bone[i].b] + bone[i].a);
}
}
printf("%d\n", dp[V]);
}
return 0;
}