首页 > 代码库 > 二维背包（钟神想要的）（不是DP）
二维背包（钟神想要的）（不是DP）
【问题描述】
背包是个好东西，希望我也有。
给你一个二维的背包，它的体积是? × ?。现在你有一些大小为1× 2和1×
3的物品，每个物品有自己的价值。你希望往背包里面装一些物品，使得它们的
价值和最大，问最大的价值和是多少。
【输入格式】
第一行一个整数?代表该测试点的数据组数。
对于每组数据，第一行有四个整数?,?,? 1 ,? 2 ，其中? 1 ,? 2 分别代表大小为
1× 2和大小为1 × 3的物品个数。
1 × 2 接下来一行有? 2 个数代表每个1 × 3物品的价值。
【输出格式】
对于每组询问，输出能够达到的价值最大值。
【样例输入】
1
2 3 2 2
1 2
1 2
【样例输出】
4
【样例解释】
庙里有座山，其实就是钟神。
【数据规模与约定】
2,? 1 ,? 2 ≤ 100。
70%的数据，?,? ≤ 100,? 1 ,? 2 ≤ 2000。
对于100%的数据，1 ≤ ? ≤ 10,1 ≤ ?,? ≤ 500,0 ≤ ? 1 ,? 2 ≤ 10000。
思路：
这题好恶心的我跟你讲；
做这个题的时候第一个反映是DP，然后风风火火的去打二维背包模板
打完回来一看傻了眼（这告诉我们要认真读题）
后来才知道这个题是个前缀和+枚举
那
怎么枚举呢？
这样枚举
判断体积为3的物品最多能放多少个
然后从0开始循环到max3
每次循环都用总体积减去已经放下的体积为3的物品的总体积
然后记录一下最大的ans就好了
恩
这是一个20分的做法
那
满分的做法呢？
满分的做法还要加一个小小的判断
现在我们想一下，所有的物体不能被拆分或者弯折
所以物体的长度一定要有足够的空间长度
但是
如果背包的长度==2或者背包的宽度==2
这时长度为3的物品就只能竖着放或者横着放
如果背包的宽度为2而长度为3的倍数（包括0）+2
这时最多能放下的体积为3的物体的个数为(n*m-4)/3
所以
如果一个背包的满足((m==2||n==2)&&m%3==2&&n%3==2)
则
能放下的体积为3的物品的个数为(n*m-4)/3
说到这基本就可以ac了
但是
不要急着去写代码
还有一个很重要的条件
就是个数最多不能超过体积为3的物品的总个数
或者是体积为2的物品的总个数
来，上代码：
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int T,sum2[10001],sum3[10001],n,m,n2,n3;int min2,min3,max2,max3,sq,ans=0,kcc;char ch;void qread(int &x){ x=0;ch=getchar(); while(ch>‘9‘||ch<‘0‘) ch=getchar(); while(ch<=‘9‘&&ch>=‘0‘){x=x*10+(int)(ch-‘0‘);ch=getchar();}}bool cmp(int a,int b){return a>b;}int main(){ qread(T); while(T--) { ans=0,min2=0,min3=0; qread(n),qread(m),qread(n2),qread(n3); for(int i=1;i<=n2;i++) qread(sum2[i]); for(int i=1;i<=n3;i++) qread(sum3[i]); sort(sum2+1,sum2+n2+1,cmp); sort(sum3+1,sum3+n3+1,cmp); for(int i=1;i<=n2;i++) sum2[i]+=sum2[i-1]; for(int i=1;i<=n3;i++) sum3[i]+=sum3[i-1]; sq=n*m; if((n%3==2&&m%3==2)&&(n==2||m==2)) max3=(sq-4)/3; else max3=sq/3; int kol=0; max3=min(max3,n3); for(int i=min3;i<=max3;i++) { kol=0; kol+=sum3[i]; kcc=(sq-(i*3))/2; kcc=min(n2,kcc); kol+=sum2[kcc]; ans=max(ans,kol); } printf("%d\n",ans); } return 0;}
二维背包（钟神想要的）（不是DP）