http://ac.jobdu.com/problem.php?id=1364
经典01背包，没有用空间逆序优化。
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4 int S,C;
5 int force[102];
6 int space[102];
7 int mat[102][1002];
8 int max(int a,int b)
9 {
10 return a>b?a:b;
11 }
12 int main()
13 {
14 while(scanf("%d%d",&S,&C)!=EOF){
15 int i;
16 for(i=1;i<=C;i++){
17 scanf("%d%d",&space[i],&force[i]);
18 }
19 memset(mat,0,sizeof(mat));
20 int j;
21 for(i=1;i<=C;i++)
22 for(j=0;j<=S;j++){
23 if(j>=space[i])
24 mat[i][j]=max(mat[i-1][j-space[i]]+force[i],mat[i-1][j]);
25 else mat[i][j]=mat[i-1][j];
26 }
27 printf("%d\n",mat[C][S]);
28 }
29 }