本文为大型题解集

X1291 数字组合
X1273 【例9.17】货币系统
P1077 摆花

X1291 数字组合

01背包求方案数。here

初探

定义状态： $f_{i,j}$ 表示前 $i$ 个数总和为 $j$ 的方案数。

那么，对于一个物品，只有选与不选两种情况（当然费用比承重大一定不选）。

易得状态转移方程：

f_{i,j}=\begin{cases} f_{i-1,j}+f_{i-1,j-w_i} & w_i\le j \\\ f_{i-1,j} & w_i>j \end{cases}

即，前 $i$ 个数总和为 $j$ 的方案数与前 $i-1$ 个数有关。前 $i$ 个数总和为 $j$ 的方案数为前 $i-1$ 个数总和为 $j$ 的方案数与前 $i$ 个数总和为 $j-w_i$ 的方案数之和。即不入选这个数字与入选这个数字的方案数之和，加法原理。

初始化：前 $0$ 个数总和为 $0$ 的方案数为一（只有什么也不选）。

CODE：

f[0][0]=1;
for(int i=1;i<=n;i++)
	for(int j=0;j<=m;j++)
	{
		if(a[i]<=j)
			f[i][j]+=f[i-1][j-w[i]];
		f[i][j]+=f[i-1][j];
	}

时间复杂度与空间复杂度皆为 $O(nm)$ 。

前 $i$ 个数总和为 $j$ 的方案数与前 $i-1$ 个数有关。

因此，可以对此优化，直接滚动成一维，把 $i$ 的那一维消掉。

CODE：

f[0]=1;
for(int i=1;i<=n;i++)
	for(int j=m;j>=w[i];j--)
		f[j]+=f[j-w[i]];

空间复杂度降为 $O(m)$ 。

注意，内层循环要逆序。这和01背包的逆序原因类似。

完全背包求方案数。here

与完全背包类似，内层循环改为正序即可。这和完全背包的正序原因类似。

CODE：

f[0]=1;
for(int i=1;i<=n;i++)
	for(int j=w[i];j<=m;j++)
		f[j]+=f[j-w[i]];

这是个分组背包！为什么呢？

为了在门口展出更多种花，规定第 $i$ 种花不能超过 $a_i$ 盆，摆花时同一种花放在一起。

第 $i$ 种花可以放不超过 $a_i$ 盆的任意盆。相当于第 $i$ 组花有许多捆在一起的花，标号 $1$ 至 $a_i$ 。第 $j$ 号有 $j$ 盆花捆着。每组中的花只能选一个。

f[0]=1;
for(int i=1;i<=n;i++)
	for(int j=m;j>=0;j--)
		for(int k=1;k<=a[i];k++)//标号1至a_i
			if(j>=k)
			    f[j]+=f[j-k];//第j号有j盆花捆着

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/dd819f9a09a1/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158