小P寻宝记——粗心的基友

2019-11-10 18:07:19

字体：大中小

来源：转载

供稿：网友

PRoblem Description

这对好基友他们在经历无数的艰难险阻后，终于找到了宝藏。无奈的是这一对好基友竟然是一样的粗心，又忘记了带一个大一点的包包，可惜啊、、选择又出现了啊、、已知包的体积是v，每种宝贝只有一个，宝贝的体积是pi，价值是wi。求出这对粗心的基友可以最多带走价值多少的宝藏。

Input

输入数据有多组。每组第一行有两个正整数n(n <= 10000)和v(v <= 10000)分别表示n种宝贝和包的体积。接下来n行，每行有两个正整数vi， wi。分别表示每种宝藏的体积vi （vi<=1000）,价值wi(wi<=1000)。

Output

这对基友所能带走的最多的宝藏。

Example Input

5 10 1 52 43 34 25 1Example Output
14Hint
01背包问题， 提交时总是runtime error 好烦。
01 #include<stdio.h>
02 #include<string.h>
03 int f[10004], v[10004], w[10004];
04 int max(int a, int b)
05 {
06     return a > b? a : b;
07 }
08 int main()
09 {
10     int n, V, i, j;
11     while(scanf("%d%d", &n, &V) != EOF)
12     {
13         memset(f, 0, sizeof(f));
14         memset(v, 0, sizeof(v));
15         memset(w, 0, sizeof(w));
16         for(i = 0; i < n; i++)
17             scanf("%d%d", &v[i], &w[i]);
18         for(i = 0; i < n; i++)
19         {
20             for(j = V; j >= v[i]; j--)
21             {
22                 f[j] = max(f[j], f[j - v[i]] + w[i]);
23             }
24         }
25         printf("%d/n", f[V]);
26     }
27     return 0;
28 }