小智：（灯泡一亮）每个地方都派人看守不就行了？！
“当~~~” 
菜虫：（手执八公分直径炒锅，筋）……你是白痴吗？-_-##（都派人去看守的话我们会有多少桌三缺一？！）听好了，输入格式是第一行一个正整数N（1<=N<=100）表示总共的娱乐项目数；第二行一个正整数表示规定的时间t（0<t<1000）；下面有N行，其中第i+2行有两个正整数fi（0<=fi<=100）和ti（0<ti<=100），分别表示对项目i的“喜欢度”和它所耗费的时间。输出的时候在第一行输出最大的“喜欢度”之和，下面给你一个样例：

样例输入1[复制]

3

5

1 2

5 5

4 3

样例输出1[复制]

5

来源： https://vijos.org/p/1025






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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67



#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

 
//01背包二维正写写法

int p[107],w[107],dp[107][1007];


int main()

{

    int N,T;


    scanf("%d%d",&N,&T);


    for(int i=1;i<=N;i++)


    {


        scanf("%d%d",&p[i],&w[i]);


    }


    memset(dp,0,sizeof(dp));


    for(int i=1;i<=N;i++)


    {


        for(int j=0;j<=T;j++)


        {


            if(j>=w[i])


                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);


            else


                dp[i][j] = dp[i-1][j];


        }


    }


    printf("%d",dp[N][T]);

}
 
//01背包二维逆写写法

int p[107],w[107],dp[107][1007];


int main()

{

    int N,T;


    scanf("%d%d",&N,&T);


    for(int i=1;i<=N;i++)


    {


        scanf("%d%d",&p[i],&w[i]);


    }


    memset(dp,0,sizeof(dp));


    for(int i=1;i<=N;i++)


    {


        for(int j=T;j>=0;j--)


        {


            if(j>=w[i])


                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);


            else


                dp[i][j] = dp[i-1][j];


        }


    }


    printf("%d",dp[N][T]);

}
 
//01背包1维写法，只能逆写

int p[107],w[107],dp[1007];


int main()

{

    int N,T;


    scanf("%d%d",&N,&T);


    for(int i=1;i<=N;i++)


        scanf("%d%d",&p[i],&w[i]);


    memset(dp,0,sizeof(dp));


    for(int i=1;i<=N;i++)


        for(int j=T;j>=w[i];j--)


            dp[j] = max(dp[j],dp[j-w[i]]+p[i]);


    printf("%d",dp[T]);

}



来源： http://tool.oschina.net/highlight