背包問題，0-1背包問題

背包問題，0-1背包問題

貪心

描述

現在有很多物品（它們是可以分割的），我們知道它們每個物品的單位重量的價值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<stdio.h>
 2 typedef struct value
 3 {
 4     int v;/*價值*/
 5     int w;/*重量*/
 6 }thing;
 7 int main()
 8 {
 9     int n;
10     scanf("%d",&n);
11     while(n--)
12     {   
13         int s,m,j,i=0,sumv=0,sumw=0;
14         scanf("%d%d",&s,&m);
15         thing a[s],t;
16         while(i!=s)
17         {
18             scanf("%d%d",&a[i].v,&a[i].w);
19             i++;
20         } 
21         for(i=0;i<s-1;i++)
22             for(j=i;j<s;j++)
23             {
24                 if(a[i].v<a[j].v)
25                 {
26                     t=a[i];
27                     a[i]=a[j];
28                     a[j]=t;
29                 }
30             }
31         int ww=0,vv=0;
32         i=0;
33         while(sumw<m)
34         {
35             ww=sumw;
36             vv=sumv;
37             sumw=sumw+a[i].w;
38             sumv=sumv+a[i].w * a[i].v;
39             i++;
40             while(i==s)
41                 break;
42         }
43         if(sumv>m)
44               sumv=vv+(m-ww)*a[i-1].v;
45         printf("%d\n",sumv);
46     }
47 }