【题解】洛谷P1466[USACO2.2]集合Subset Sums(0/1背包详解)

题目

洛谷P1466[USACO2.2]集合Subset Sums

题解

此题关键在于将“能划分成几种子集”转化为“有多少子集的和是全集和的一半”。由于和不大,所以可以考虑递推。这个问题的模型是“0/1背包问题”:从一些物品中选取一部分,装满背包。

优化:此题的数据范围比较友好,如果n比较大,那么f数组的空间开销就会比较大,所以考虑使用“滚动数组”。容易发现每个阶段j只与上一个阶段j-1有关,所以只需要两个数组下标,一个表示当前阶段,另一个表示上一阶段。

滚动的那一维要在循环外侧,因为要把这一阶段的所有信息处理完,才能进入下一阶段。

继续优化(背包问题的精髓):首先,将上面的代码进行一些等价的修改。(只显示修改的部分)

考虑之前可以滚动数组优化的原因:f[][j-2]不会影响到f[][j]和f[][j-1]。

在这份代码中,f[i][cur]=f[i][cur^1] 相当于复制操作(即相当于一个一维数组保持不变),关键在于下一句的更新。

那么,是否可以让f[i][cur]不受f[i-j][cur^1]的影响,而是直接从f[i-j][cur]本身更新?

这时可以考虑“倒序循环”:更新完f[i][cur]后,不用更换cur^1,而是直接在f[i][cur]上继续更新,省去了复制操作,在令i从大到小循环,用f[i-j][cur]更新f[i][cur],由于是倒序,f[i][cur]在更新完后,不会受到后续操作的影响。那么就可以直接舍弃[cur]这一维。

注意j的循环仍然要在外侧。

Subscribe
提醒
guest
3 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月12日 下午3:53

【小白解析】
背包问题的经典之处在于“取”与“舍”:放在此题中,在需要的子集元素和为n,现有元素和为x时,对于集合中新遍历到的每一个数字j(由于初始数列是公差为1的自然数列,此时程序的考虑范围是1到j),程序都应当发问:
A:如果将j包含在内,是否能使x+j==n?
B:如果不包含j,在先前的考虑范围(即1到j-1)中是否有现成的、和为n的排列供我们使用?

同时还有两大要点;
C:在考虑A的情况下同时需考虑B,有现成的排列方式何乐而不为;
D:如果已知x+j>n,则必须直接放弃加上j,不需要考虑A;

在具体程序中,我们通过从小到大堆积i以达到i==sum/2的要求。第一段代码的14行既是对要点D的判断:在此情况下,若j已大于现阶段需要的i,自然不需要加上j,反之则需要。15行则是对要点C的阐述。

优化代码的部分分别从要点C和数组滚动上出发。因为我们不需要追寻范围为1到y(1<=y<=j-1)的任何结果,所以可以覆盖之前的选择。第二段代码主要通过二维数组(仅两层)表示过去状态与现状态,其过程如同在两个维度间跳跃:程序执行完维度1,跳跃至维度2(现在),维度1成为过去;程序执行完维度2,跳跃至维度1(成为现在),维度2成为过去……

第三段代码主要借助要点C,省去了多余的、无论如何都会执行的一个操作(即从范围1到j-1中“剽窃”现有的子集数量)。

第四段代码通过倒叙循环省略了“维度跳跃”,同时其倒叙性质在改变过去数据的同时,不影响现在数据的发展。
*话说这些代码中的^可以替换成~吗?好像都满足让cur在0与1间转换的要求。

cyx
cyx
Reply to  Martin
2020年8月12日 下午4:54

好像是不行,抱歉。