开心的小明（背包）

 1 #include<stdio.h>
 2 #include<string.h>
 3 struct Case{
 4     int price,importance;
 5 }data[25];
 6 int main(){
 7     int N,m,T,bag[30000],a,b;
 8     scanf("%d",&T);
 9     while(T--){memset(bag,0,sizeof(bag));
10         scanf("%d%d",&N,&m);
11         for(int i=0;i<m;++i)scanf("%d%d",&a,&b),data[i].price=a,data[i].importance=a*b;
12         for(int i=0;i<m;++i){
13         for(int j=N;j>0;j--){
14                 if(j>=data[i].price){ 
15             if(bag[j-data[i].price]+data[i].importance>bag[j])bag[j]=bag[j-data[i].price]+data[i].importance;    }
16             }
17         }
18         printf("%d
",bag[N]);
19     }
20     return 0;
21 }