自动搬运

查看原文

来自洛谷，原作者为

	guoshengyu1231 **

搬运于2025-08-24 21:17:03，当前版本为作者最后更新于2025-03-16 15:45:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目传送门

初步思考

看了看题面，可以知道这应该是一道状态压缩 dp 的模版题，先不管题目中的限制条件，反正这一定是一道状态压缩 dp 的题目。不妨先假设 $s$ 等于 $0$，此时就是一道纯状态压缩 dp 的题目，那我们就先考虑状态压缩 dp。

具体步骤

确定状态

用一个结构体存储数组 $dp$，再定义状态 $S$ 为要处理哪些书，此时的 $dp$ 数组有两个量。其中第一个量是 $x$，代表在状态 $S$ 下最少需要几个包裹。还有一个量是 $t$，代表在 $x$ 最小的情况下，最空的包裹已经用了多少容量。其中 $dp_S$ 表示在状态 $S$ 下使这两个量最优。$\\$
具体的，定义 $x$ 和 $t$ 这两个量最优，设最优的 $x$ 和 $t$ 为 $sx$ 和 $st$，满足在状态 $S$ 下，$\forall x$ 和 $\forall t$ 都不满足 $x<sx \lor x=sx \land t<st$。$\\$

状态转移

设函数 $\operatorname{cmp}$ 会在两个状态中返回较优的状态，其中，一个状态是否最优取决于状态中的两个量是否最优。

方程推导

想象一下，我们要在原来的状态中新添加一本书，那我们肯定是要把它放进最空的包裹里，如果连最空的包裹都放不下，那就只能新建一个包裹来放了，所以我们可以计算出新状态，公式如下：

$$newS_x=\begin{cases} oldS_t+a_i>m ,&oldS_x+1 \\ oldS_t+a_i\le m,&oldS_x \\ \end{cases}$$

$\\$

$$newS_t=\begin{cases} oldS_t+a_i>m ,&a_i \\ oldS_t+a_i\le m,&oldS_t+a_i \\ \end{cases}$$

其中 $i\in S$，$oldS$ 表示老状态，$newS$ 表示新状态。 $\\$ 那么状态转移方程就显而易见了，每次枚举 $i$ 时算出新状态，再将所有的新状态取最优。

状态转移方程

$$dp_S=\operatorname{cmp}(dp_S,dp_{newS})$$

示例

样例输入：

3 10
4 8 2

此时的 $dp$ 数组如下：

状态S	最优答案
0 0 1（1）	1.4
0 1 0（2）	1.8
0 1 1（3）	2.4
1 0 0（4）	1.2
1 0 1（5）	1.6
1 1 0（6）	1.10
1 1 1（7）

格式说明：最优答案用 $x.t$ 这样的格式表示。

$\\$

现在我们已经知道了状态 $7$ 之前的所有状态的最优答案，现在我们要算出状态 $7$ 的最优答案，通过枚举 $7$ 的所有二进制位，我们可以知道状态 $7$ 可以由状态 $6$，$5$，$3$ 转移而来，可分为三组计算，分别为（$1.10$，$4$），（$1.6$，$8$），（$2.4$，$2$）。根据新状态计算公式，可得计算结果分别为 $2.4$，$2.8$，$2.6$。其中最优的答案是 $2.4$。这里只做一个示例，你们可以自己动手试一下，算一算，加深理解。

$\\$

到目前为止，主要问题其实已经解决了。但还剩下一个问题，那就是 $s\ne 0$ 的情况。这个问题其实很简单，只需要并查集统计需要打包在一起的书，将它们的质量都加起来然后合并成一本书就行啦！

代码

其实我讲的应该算清晰了的，你们可以先自己试试，不懂的再看代码。

#include<bits/stdc++.h> 
using namespace std;
int n1,m,a1[25],s,num,n,a[25],fnum;
int f[25];
int find(int x)
{
	if(x==f[x]) return x;
	return f[x]=find(f[x]);
}
bool cmp(int x1,int y1,int x2,int y2)
{
	if(x1==y1) return x2>y2;
	return x1>y1;
}
struct{
	int x,t;
}dp[1<<23];
int main()
{
	cin>>n1>>m;
	for(int i=1;i<=n1;i++) f[i]=i;
	for(int i=1;i<=n1;i++) cin>>a1[i];
	cin>>s;
	while(s--)
	 {
		cin>>fnum;
		if(cin.get()=='\n')	continue;//若输入的是换行，跳过。 
		while(cin>>num)
		 {
			f[find(num)]=find(fnum);//并查集。	
			if(cin.get()=='\n') break;//同上。 
		 }
	 }
	for(int i=1;i<=n1;i++)
	 if(f[i]!=i)
	  {
		a1[f[i]]+=a1[i];
		a1[i]=0;
	  }
	for(int i=1;i<=n1;i++)
	 if(a1[i]) a[++n]=a1[i];
/*  并查集部分还是很好理解的，这里不再过多赘述。*/ 
	 
/*----------------------DP----------------------*/
	
	for(int i=1;i<=n;i++)
	 {
		dp[(1<<i-1)].x=1;
		dp[(1<<i-1)].t=a[i];
	 }
	//初始化，应该不用多讲了吧。 
	for(int s=1;s<(1<<n);s++)
	 {		
		if(!(s&s-1)) continue;
		dp[s].x=INT_MAX;//一定要赋初值！ 
		for(int i=1;i<=n;i++)	
		 if((s>>i-1)&1)
		  {
			int x=dp[s^(1<<i-1)].x;
			int t=dp[s^(1<<i-1)].t;
			if(t+a[i]>m)
			 {
				x++;
				t=a[i];	
			 }
			else t+=a[i];
			if(cmp(dp[s].x,x,dp[s].t,t))
			 {
				dp[s].x=x;
				dp[s].t=t;	
			 }
		  }
	 }
	cout<<dp[(1<<n)-1].x;
	return 0;
}