凝视
【问题描述】
背包是个好东西,希望我也有。
给你一个二维的背包,它的体积是N× M。现在你有一些大小为1 × 2和1 × 3的物品,每个物品有自己的价值。你希望往背包里面装一些物品,使得它们的价值和最大,问最大的价值和是多少。
【输入格式】
第一行一个整数T代表该测试点的数据组数。
对于每组数据,第一行有四个整数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
【样例解释】
庙里有座山。
【题目分析】
算了,我不分析了,都在代码里了
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int T; int n,m,n1,n2; int a[10001],b[10001]; int c1[10001],c2[10001];//c1[i]表示用前i个大的1*2的价值,c2[i]->1*3 int ans=0; int ans1=0,ans2=0;//ans1是1*3的个数,ans2是1*2的个数,这里不要弄乱了 bool cmp(int x,int y) { return x>y; } int main() { freopen("eyesight.in","r",stdin); freopen("eyesight.out","w",stdout); scanf("%d",&T); while(T--) { ans=0; c1[0]=0;c2[0]=0; scanf("%d%d%d%d",&n,&m,&n1,&n2); for(int i=1;i<=n1;i++) scanf("%d",&a[i]); for(int i=1;i<=n2;i++) scanf("%d",&b[i]); sort(a+1,a+n1+1,cmp); sort(b+1,b+n2+1,cmp); for(int i=1;i<=n1;i++) c1[i]=c1[i-1]+a[i]; for(int i=1;i<=n2;i++) c2[i]=c2[i-1]+b[i]; if(n>m) swap(n,m); if(n==2&&m%3==2)//这里特判一下2*2出来的4个格子的情况 { for(ans1=0;ans1*3<=n*m-4;ans1++) //就只能放两个1*2的 { } ans2=(n*m-3*ans1)/2, ans=max(ans,c1[min(ans2,n1)]+c2[min(ans1,n2)]); } else//这里就是正常情况下 { for(ans1=0;ans1*3<=n*m;ans1++) ans2=(n*m-3*ans1)/2, ans=max(ans,c1[min(ans2,n1)]+c2[min(ans1,n2)]); } printf("%d ",ans); } fclose(stdin);fclose(stdout); return 0; } /* 1 5 5 4 10 10 10 10 10 100 100 100 100 100 100 100 100 100 100 */