PRoblem Description

多組輸入。

對(duì)于每組輸入，第一行有兩個(gè)整數(shù)N，X（1 < = N < = 100，1 < = X < = 1000），分別表示哈士奇的數(shù)量和高數(shù)巨的錢(qián)數(shù)

對(duì)于每組數(shù)據(jù)，輸出一個(gè)整數(shù)，表示高數(shù)巨最多可以獲得的萌值，每組輸出占一行

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
 
上午學(xué)長(zhǎng)剛講的背包問(wèn)題， 屬于01背包
關(guān)鍵代碼
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