PRoblem Description

Input

Output

Example Input

5 10 1 52 43 34 25 1
Example Output
14
Hint
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
}