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
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
int main(int argc,char**argv){
    int m,n,k,j,max;
    int*need,*value;
    unsigned short*result;
    scanf("%d%d",&n,&m);
    need=(int*)malloc(sizeof(int)*n);
    value=(int*)malloc(sizeof(int)*n);
    if(need==NULL||value==NULL)
        return -1;
    for(k=0; k<n; k++)
        scanf("%d%d", need+k,value+k);
    result=(unsigned short*)malloc(sizeof(short)*m);
    if(result==NULL)
        return -1;
    memset(result, 0, m*sizeof(short));
    max=0;
    for(k=0; k<n; k++){
        for(j=m-1;j>=need[k]; j--){
            if(result[j]<result[j-need[k]]+(unsigned short)value[k]){
                result[j]=result[j-need[k]]+(unsigned short)value[k];
                //if(max<result[j])
                    //max=result[j];
            }
        }
    }
    max=result[m-1];
    printf("%d\n", max);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX