【问题描述】
背包是个好东西，希望我也有。
给你一个二维的背包，它的体积是N*M。现在你有一些大小为1*2和1*3的物品，每个物品有自己的价值。你希望往背包里面装一些物品，使得它们的价值和最大，问最大的价值和是多少。
【输入格式】
第一行一个整数代表该测试点的数据组数。
对于每组数据，第一行有四个整数N，M，n1，n2，其中n1，n2分别代表大小为1*2和大小为1*3的物品个数。
接下来一行有n1个数代表每个1*2物品的价值。
接下来一行有n2个数代表每个1*3物品的价值。
【输出格式】
对于每组询问，输出能够达到的价值最大值。
【样例输入】
1
2 3 2 2
1 2
1 2
【样例输出】
4
【样例解释】
庙里有座山。
【数据规模与约定】
对于的数据，N,M<=10,n1,n2<=100。
对于的数据，N,M<=100,n1,n2<=2000。
对于的数据，1<=T<=10,1<=N,M<=500,0<=n1,n2<=10000。
思路：
贪心的做法，先计算能完整放入的1*3的个数，再枚举所有的情况找最大值，并用前缀和记录数量一定时最大价值的情况。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 using namespace std; 6 int n,m,n1,n2,t,x[10001],y[10001]; 7 int cmp(int a,int b) 8 {return a>b;} 9 int main() 10 { freopen("eyesight.in","r",stdin); 11 freopen("eyesight.out","w",stdout); 12 cin>>t; 13 while(t--) 14 { memset(x,0,sizeof(x)); 15 memset(y,0,sizeof(y)); 16 cin>>n>>m>>n1>>n2; 17 for(int i=1;i<=n1;i++)cin>>x[i]; 18 for(int i=1;i<=n2;i++)cin>>y[i]; 19 sort(x+1,x+n1+1,cmp); 20 sort(y+1,y+n2+1,cmp); 21 for(int i=1;i<=n1;i++)x[i]+=x[i-1]; 22 for(int i=1;i<=n2;i++)y[i]+=y[i-1]; 23 int di2ta; 24 if(n%3==2&&m%3==2&&(m==2||n==2))di2ta=4; 25 else di2ta=m*n%3; 26 int ans=0,limit=min(n2,(m*n-di2ta)/3); 27 for(int i=0;i<=limit;i++) 28 ans=max(ans,y[i]+x[min(n1,(n*m-3*i)>>1)]); 29 cout<<ans<<endl; 30 } 31 }
