©2020-2024 ioDraw All rights reserved,
Privacy Policy
Problem Description
多组输入。
对于每组输入，第一行有两个整数N，X（1 < = N < = 100，1 < = X < = 1000），分别表示哈士奇的数量和高数巨的钱数
对于每组数据，输出一个整数，表示高数巨最多可以获得的萌值，每组输出占一行
Example Input
2 100 50 20 60 40 3 100 20 55 20 35 90 95 1 10 20 50
Example Output
40 95 0
Hint
上午学长刚讲的背包问题， 属于01背包
关键代码
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
01 #include<stdio.h>
02 #include<string.h>
03 int max(int a, int b);
04 int main()
05 {
06 int n, x, p[111], m[111], j, i;
07 int a[1005];
08 while(scanf("%d%d", &n, &x) != EOF)
09 {
10 memset(a, 0, sizeof(a));
11 memset(p, 0, sizeof(p));
12 memset(m, 0, sizeof(m));
13 for(i = 1; i <= n; i++)
14 scanf("%d%d", &p[i], &m[i]);
15 for(i = 1; i <= n; i++)
16 {
17 for(j = x; j >= 0; j--)
18 if(j >= p[i])
19 a[j] = max(a[j], a[j - p[i]] + m[i]);
20 }
21 printf("%d\n", a[x]);
22 }
23 return 0;
24 }
25 int max(int a, int b)
26 {
27 return a > b? a : b;
28 }
29