自动搬运

查看原文

来自洛谷，原作者为

	bingzhi314 心有所向，可事与愿违

搬运于2025-08-24 21:37:23，当前版本为作者最后更新于2025-07-23 15:51:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目

经过多次尝试后，发现用堆是做不出来了。

于是还是用了背包。

由题可见，本题用分组

于是可写以下代码：

for(int i=1;i<=n;i++){  
      for(int j=0;j<=m;j++){//注：
  			for(int k=1;k<=v[i][0];k++){
  				if(v[i][k]<=j){
  					f[i][j]+=f[i-1][j-v[i][k]];
    		    }
    		}
       }
}

虽不允许不选第i组的物品，但j很小时可能会存在某些组的物品一个也放不进的情况，但是这不影响我们要求的答案。因为，题目描述的前x小的体积和，在遍历到他们（某个j）时，每个组肯定肯定存在物品v[i]<j，而每个组都能选出一个物品，因此不存在某个组选不出物品的情况 。这是可推的。 但交上去，却惊奇的发现《100pts》。

这个出现是因为有时候long long数组溢出变负

故：

for(int i=1;i<=n;i++){  
      for(int j=0;j<=m;j++){//注：
			for(int k=1;k<=v[i][0];k++){
				if(v[i][k]<=j){
					f[i][j]+=f[i-1][j-v[i][k]];
					if(f[i][j]>c){
                      	  f[i][j]=c;
                  	}
            	}
		    }
		}
	}

大于k的减去。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,x,c,m; 
int v[110][110];
long long f[110][10010];
int main(){
	f[0][0]=1;
	scanf("%d%d",&n,&c);
	for(int i=1;i<=n;i++){
		scanf("%d",&v[i][0]);
		int ma=-0x3f3f3f3f;
		for(int j=1;j<=v[i][0];j++){
			scanf("%d",&v[i][j]);
			ma=max(ma,v[i][j]);
		}
		m+=ma;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int k=1;k<=v[i][0];k++){
				if(v[i][k]<=j){
					f[i][j]+=f[i-1][j-v[i][k]];
					if(f[i][j]>c){
                      	  f[i][j]=c;
                  	}
            	}
		    }
		}
	}
	int cnt=0;
	for(int j=1;j<=m;j++){
		if(f[n][j]>0){
			int t=f[n][j];
			while(t>0&&cnt<c){
				cnt++;
				printf("%d ",j);
				t--;
			}
		}
	}
	puts("");//记得换行，自求多福吧。。
	return 0; 
}