现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。

第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；
随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。

输出每组测试数据中背包内的物品的价值和，每次输出占一行。

1
3 15
5 10
2 8
3 9

65

1 #include
2 #include
3 typedef struct NODE
4 {
5 int v , w;
6 }Node;
7 Node array[11];
8
9 int comp(const void *a , const void * b)
10 {
11 return (*(Node *)b).v - (*(Node *)a).v ;
12 }
13 int main()
14 {
15 int i;
16
17 scanf("%d" , &i);
18 while(i--)
19 {
20 int a , b , j, sum = 0;
21 scanf("%d %d" , &a , &b);
22 for(j = 0 ; j < a ; j++) 23 { 24 scanf("%d %d" , &array[j].v , & array[j].w ); 25 } 26 qsort(array , a , sizeof(Node) , comp); 27 for(j = 0 ; j < a ; j++) 28 { 29 if(array[j].w > b)
30 {
31 sum += b * array[j].v ;
32 break;
33 }
34 b -= array[j].w;
35 sum += array[j].v * array[j].w ;
36 }
37 printf("%d\n" , sum);
38 }
39 return 0;
40 }