NYOJ背包问题

 1 #include <stdio.h>
 2 struct group{
 3     
 4     int value;
 5     int weight;
 6 
 7 };
 8 void Sort(group bag[],int num)
 9 {
10     int i,j;
11     group temp;
12     for(i=1; i<=num-1; i++)
13         for(j=1; j<=num-i; j++)
14             if(bag[j+1].value>bag[j].value)
15             {
16                 temp=bag[j];
17                 bag[j]=bag[j+1];
18                 bag[j+1]=temp;
19             }
20 }
21 int main()
22 {
23     int i,n,num,capacity,sum,m;
24     group bag[12];    
25     scanf("%d",&n);
26     while(n--)
27     {
28         scanf("%d%d",&num,&capacity);
29         for(i=1; i<=num; i++)
30             scanf("%d%d",&bag[i].value,&bag[i].weight);
31         Sort(bag,num);
32         m=sum=0;
33         for(i=1; i<=num; i++)
34         {
35             if(m+bag[i].weight<=capacity)
36             {
37                 m+=bag[i].weight;
38                 sum+=bag[i].weight*bag[i].value;
39             }
40             else
41             {
42                 sum+=bag[i].value*(capacity-m); //因为m+bag[i].weight>capacity,所以bag[i].weight>capacity-m,不必考虑物品份数不够
43                 break;
44             }
45         }
46         printf("%d
",sum);
47     }    
48     return 0;
49 }

View Code

思想是怎样使放入的物体的价值总和最大。
一开始想复杂，以为不仅要贪心，还要考虑最适，纠结半天。。

看了看别人的代码，明白。可以这样理解，其实可以把这些要装入的物品分解成一根根细线（3D的样子~~，重量可以分割），然后把它们填入一个圆筒里，这样你不会先装入价值小的，而是努力把价值大的细线填入，这便是单纯的贪心了。直到填满或物品都放进去。