自动搬运

查看原文

来自洛谷，原作者为

	zhm080507 九天游奕，太岁至德，杀伐威权殷元帅急急如律令

搬运于2025-08-24 22:38:41，当前版本为作者最后更新于2024-09-30 20:28:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意描述

要在权值为 $[-m,m]$ 中选若干个物品，使它们的权值之和为 $L$，并使它们的个数之和尽可能大。

算法分析

• 首先我们可以发现选取物品的最优一定是小的多选，那我们可以先将全部都选进来，然后再从大到小删除；

  最后的结果 $sum$ 一定是属于 $[L-m,L+m]$ 的。

if(sum>L){//如果大了，从m开始删 
		for(int i=2*m;i>m;i--){
			tmp=sum-L;
			b[i]-=min(tmp/(i-m),a[i]);//注意上限 
			sum-=(i-m)*(a[i]-b[i]);
		}
	}else{//如果小了，从-m删 
		for(int i=0;i<m;i++){
			tmp=L-sum;
			b[i]-=min(tmp/(m-i),a[i]);
			sum-=(i-m)*(a[i]-b[i]);
		}
	}
	//a为总数，b为用了的个数 

• 现在我们的目标就变成了在当前基础上进行调整，使最后的合并结果变为 $L$。

  我们容易发现对于每一次跳动的最大限度是 $m$，所以一定存在策略能使 $sum$ 维持在 $[L-m,L+m]$ 中； 而一个当前的 $sum$，在第二次出现时经过调整，结果一定不优；

  由此，对于每个物品，因为其每次使用造成的影响至少为 $1$，所以至多有 $m$ 个变化是有效的，所以得出 $sum$ 的有效值域为 $[L-m^2,L+m^2]$，所以在这里面进行多重背包时，物品个数最多为 $m^2$ 个。

  siz=m*m*2;
  	memset(f,-0x3f,sizeof(f));
  	/*
  	接下来在(L-m^2,L+m^2)的值域中跑多重背包 
  	对于物品个数：
  		因为对于一个在(L-m^2,L+m^2)中的值，我们最多只能到达一次， 
  	因为多次变化后答案更劣。而每一个物品加入或删除至少变化一，所
  	以对于每种物品最多考虑m^2个 
  	*/ 
  	tmp=m*m-L+sum;f[tmp]=0;//背包边界 
  	for(int i=0;i<=2*m;i++)
  		f[tmp]+=b[i];//初始化，当前情况用了多少 
  	for(int i=0;i<=2*m;i++){
  		if(i==m) continue;//价值为0的物品显然全选 
  		if(b[i])//如果有用了的，考虑删除 
  			add(-(i-m),-1,min(b[i],(ll)siz)) ;
  		if(a[i]-b[i])//如果有没用的，考虑添加 
  			add(i-m,1,min(a[i]-b[i],(ll)siz)) ;
  	}
  

  另外，对于多重背包因为复杂度为 $O(m*(m^2)^2)=O(m^5)$，所以用二进制优化为$O(m^3log(m^2))$。

  void add(ll w,ll v,int c){
  	//w表示当前操作一次对sum的影响，v表示对结果的影响，c表示物品个数
  	if(w>0){
  		for(int s=1;c>0;c-=s,s<<=1){
      	int k=min(s,c);//二进制优化多重背包 
  		for(int i=siz;i>=k*w;i--)
      		f[i]=max(f[i],f[i-k*w]+k*v);
      	//倒序跑01背包
      }
  	}else{
  		for(int s=1;c>0;c-=s,s<<=1) {
  			int k=min(s,c);
  		for (int i=0; i-k*w<=siz;++i)
  			f[i]=max(f[i],f[i-k*w]+k * v);
  		}
  	}
  }
  

• 特别的，对于超过值域范围的 $L$ 需要特判掉。

  cin>>m>>L;
  	for(int i=0;i<=2*m;i++){
  		cin>>a[i];b[i]=a[i];
  		//a为总数，b为用了的个数 
  		if(i<m) dm+=a[i]*(i-m);
  		else um+=a[i]*(i-m);
  	}//记录上下边界 
  	if(L<dm||L>um){
  		printf("impossible\n");
  		return 0;
  	}//如果超出，直接结束 
  

完整代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int M=310;
ll m,L,dm,um,tmp,sum;
ll a[M*2], b[M*2];
ll siz;
ll f[M*M*2];

void add(ll w,ll v,int c){
	//w表示当前操作一次对sum的影响，v表示对结果的影响，c表示物品个数
	if(w>0){
		for(int s=1;c>0;c-=s,s<<=1){
    	int k=min(s,c);//二进制优化多重背包 
		for(int i=siz;i>=k*w;i--)
    		f[i]=max(f[i],f[i-k*w]+k*v);
    	//倒序跑01背包
    }
	}else{
		for(int s=1;c>0;c-=s,s<<=1) {
			int k=min(s,c);
		for (int i=0; i-k*w<=siz;++i)
			f[i]=max(f[i],f[i-k*w]+k * v);
		}
	}
}

int main(){
//	freopen("greedy.in", "r", stdin);
//	freopen("greedy.out", "w", stdout);
	cin>>m>>L;
	for(int i=0;i<=2*m;i++){
		cin>>a[i];b[i]=a[i];
		//a为总数，b为用了的个数 
		if(i<m) dm+=a[i]*(i-m);
		else um+=a[i]*(i-m);
	}//记录上下边界 
	if(L<dm||L>um){
		printf("impossible\n");
		return 0;
	}//如果超出，直接结束 
	sum=dm+um;
	if(sum>L){//如果大了，从m开始删 
		for(int i=2*m;i>m;i--){
			tmp=sum-L;
			b[i]-=min(tmp/(i-m),a[i]);//注意上限 
			sum-=(i-m)*(a[i]-b[i]);
		}
	}else{//如果小了，从-m删 
		for(int i=0;i<m;i++){
			tmp=L-sum;
			b[i]-=min(tmp/(m-i),a[i]);
			sum-=(i-m)*(a[i]-b[i]);
		}
	}
	siz=m*m*2;
	memset(f,-0x3f,sizeof(f));
	/*
	接下来在(L-m^2,L+m^2)的值域中跑多重背包 
	对于物品个数：
		因为对于一个在(L-m^2,L+m^2)中的值，我们最多只能到达一次， 
	因为多次变化后答案更劣。而每一个物品加入或删除至少变化一，所
	以对于每种物品最多考虑m^2个 
	*/ 
	tmp=m*m-L+sum;f[tmp]=0;//背包边界 
	for(int i=0;i<=2*m;i++)
		f[tmp]+=b[i];//初始化，当前情况用了多少 
	for(int i=0;i<=2*m;i++){
		if(i==m) continue;//价值为0的物品显然全选 
		if(b[i])//如果有用了的，考虑删除 
			add(-(i-m),-1,min(b[i],(ll)siz)) ;
		if(a[i]-b[i])//如果有没用的，考虑添加 
			add(i-m,1,min(a[i]-b[i],(ll)siz)) ;
	} 
	if(f[m*m]<0) cout<<"impossible"<<endl;
	else cout<<f[m*m]<<endl;
	return 0;
}