UVa 1149 Bin Packing 【贪心】

题意：给定n个物品的重量l[i],背包的容量为w，同时要求每个背包最多装两个物品，求至少要多少个背包才能装下所有的物品

和之前做的独木舟上的旅行一样，注意一下格式就好了

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 #define mod=1e9+7;
12 using namespace std;
13 
14 typedef long long LL;
15 const int maxn=100005;
16 int a[maxn];
17 
18 int main()
19 
20 {
21 
22     int ncase,i,j,w,n,sum;
23     cin>>ncase;
24     int t=0;
25     while(ncase--)
26     {
27         t++;
28         sum=0;
29         memset(a,0,sizeof(a));
30         cin>>n>>w;
31         for(i=1;i<=n;i++) cin>>a[i];
32         
33         sort(a+1,a+n+1);
34         i=1;
35         j=n;
36         while(i<=j)
37         {
38             if(a[i]+a[j]<=w&&i!=j)
39             {
40                 i++;
41                 j--;
42                 sum++;
43             }
44             else
45             {
46                 j--;
47                 sum++;
48             }
49         }
50         if(t!=1) printf("
");
51         printf("%d
",sum);        
52     }
53     return 0;
54 }

View Code