P3985 不开心的金明

金明今天很不开心，家里购置的二手房就要领钥匙了，房里并没有一间他自己专用的很宽敞的房间。更让他不高兴的是，妈妈昨天对他说：“你需要购买哪些物品，怎么布置，你说了不算（有很大的限制），而且不超过W元钱。”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的W元。于是，他把每件物品规定了一个重要度整数 $p_ipi表示。他还从因特网上查到了每件物品的价格v_ivi（都是整数元）。$

妈妈看到购物单后进行了审查，要求购物单上所有的物品价格的极差（最贵的减去最便宜的）不超过3（当然金明至今不知道为什么会这样）。他希望在不超过W元（可以等于W元）的前提下，使购买的重要度总和 $p_i∑pi的最大。$

请你帮助金明设计一个满足要求的购物单，你只需要告诉我们重要度的最大的和。

输入格式

输入的第1行，为两个正整数，用一个空格隔开：

n W （其中W表示总钱数，n为希望购买物品的个数。）

从第2行到第n+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数v p （其中v表示该物品的价格，p表示该物品的重要度）

输出格式

输出只有一个正整数，为不超过总钱数的物品的重要度的总和的最大值

输入输出样例

输入 #1

输出 #1

说明/提示

$10^91≤W≤109$

$10^91≤vi≤109$

对所有的 $i=1,2,3,…,Ni=1,2,3,…,N，min(v_i) le v_i le min(v_i)+3min(vi)≤vi≤min(vi)+3.$

$p_i le 10^71≤pi≤107$

但是 n<=100,w<=10^9,

01背包的时间复杂度和空间复杂度都为O（n*w）,即超时也超空间。

01背包能得部分分

代码如下：

//纯01背包能过6个点，其他超空间和时间
//题目有一个特点最大的价格和最小价格的差值<=3 
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=100+10;
const int maxm=10000000;
int n,w;
int v[maxn],p[maxn], f[maxm];
int main(){
	scanf("%d%d",&n,&w);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&v[i],&p[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=w;j>=v[i];j--){
			if(f[j]<f[j-v[i]]+p[i]){
				f[j]=f[j-v[i]]+p[i];
			}	
			
		//	cout<<f[j]<<" ";
		}
	//	cout<<endl;
	}
	printf("%d
",f[w]);	
	return 0;
}

这里物品数量n<=100,能不能用搜索做呢？

搜索的时间复杂度是O（2^n），可以看出来也超时。

加上剪枝后，搜索能过8改点

代码如下：

//纯01背包能过6个点，其他超空间和时间
//题目有一个特点最大的价格和最小价格的差值<=3 
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=100+10;
int minn=1200000000;
int n,w,ans=0;
int v[maxn],p[maxn],sum[maxn];
void dfs(int i,int s,int c){
	if(i==n+1){
		ans=max(ans,s);
		return ;
	}
	if(c<minn) {//剪枝1，没看到效果 
		ans=max(ans,s);
		return ;
	}
	if(s+sum[n]-sum[i-1]<ans) return ;//剪枝2效果比较明显，多过了3个数据点 
	dfs(i+1,s,c);
	if(c>=v[i])dfs(i+1,s+p[i],c-v[i]);
	//
}
int main(){
	scanf("%d%d",&n,&w);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&v[i],&p[i]);
		minn=min(v[i],minn);
		sum[i]=sum[i-1]+p[i];
	}
	//cout<<minn<<endl;
	dfs(1,0,w);
	printf("%d
",ans);	
	return 0;
}

充分利用题目给定的条件（动规+贪心）：（1）题目有一个特点最大的价格和最小价格的差值<=3

（2）n件物品的价值之和肯定是>=w

//纯01背包能过6个点，其他超空间和时间
//题目有一个特点最大的价格和最小价格的差值<=3 
/*假设买100件最便宜的花费x元，则买100件最贵的花费x+3*100 
当最便宜的minn>300时，100件物品的差值最大为300，这300元一件物品也买不到
即此时，买最贵的和买最便宜的，能买的件数是一样的，不受价格影响。 
这样我们就可以使用贪心策略，按重要程度从到底来进行购买了。
题目中隐含的第二个条件：想买的东西太多了，肯定会超过妈妈限定的W元
也就是说n件物品的价值之和肯定是>=w 
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100+10;
const int maxm=340000;
int n,w,minn=2e9;
int maxx=-1;
int v[maxn],p[maxn], f[maxm];
int cmp(int x,int y){
	return x>y;
}
int main(){
	scanf("%d%d",&n,&w);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&v[i],&p[i]);
		minn=min(minn,v[i]);//求价格的最小值 
		maxx=max(maxx,v[i]);
	}
	if(minn<=300){//此时价格之和最大值303*100=30300； 
		//int t=min(w,30400);//输出结果和j的取值，注意要用最大值min(w,30300+100 )
		for(int i=1;i<=n;i++){
			for(int j=w;j>=v[i];j--){//j的值不能用w（w<10^9)，用能取到的最大值 30300+100
					f[j]=max(f[j],f[j-v[i]]+p[i]);	
			}
		}
		printf("%d
",f[w]);//输出结果注意要用最大值min(w,30300+100 ),因为题目中说物品价值之和大于W，此处可以直接使用w 
	}
	else {//此时价值之和很大，可是却不用数组了 
		int sum=0;
		sort(p+1,p+n+1,cmp);//从大到小排序
		for(int i=1;i<=w/maxx;i++) sum+=p[i]; 
		printf("%d
",sum);
	} 
	return 0;
}