分配问题

Published: December 21, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 求和分配问题

求和分配问题

求和分配问题是这样的，给定$n$个正整数$a_1,\ldots,a_n$。之后要将所有元素划分到两个集合$A,B$中，要求$A$中元素总和减去$B$中元素总和正好等于$T$，其中$T$是提前指定的数。

求和分配问题还有一种形式，就是将所有元素划分到三个集合$A,B,C$中，要求$A$中元素总和减去$B$中元素总和正好等于$T$，其中$T$是提前指定的数。这种形式相当于允许我们不考虑一部分的元素。

分成两个集合的求和分配问题的一般解法是，首先将所有数分配到集合$B$中，之后我们不断将元素从集合$B$中移动到集合$A$中。可以发现现在我们移动元素$i$，总和会增加$2a_i$。而我们希望总和提高的量正好达到$\sum_{i=1}^na_i+T$。现在问题变成了，有大小为$a_1,\ldots,a_n$的$n$块石头，以及容量正好为$(\sum_{i=1}^na_i+T)/2$的背包，问是否可能选择一部分石头正好装满背包。

而对于分成三个集合的形式，相当于第$i$个物品的价值可能是$a_i$，也可能是$2a_i$。

题目1：解决分成两个集合的求和分配问题，这里特殊的每个$a_i$都是$2$的幂次。要求回答当$T=t_1,\ldots,t_m$的时候是否有解，其中$1\leq n,m\leq 10^6$。

考虑转换过的问题，我们现在用一堆$2$的幂次，来组合一个给定的数。这个问题可以直接从低位向高位枚举，贪心解决，时间复杂度为$O(m\log_2M+n)$。

题目2：解决分成三个集合的求和分配问题，这里特殊的每个$a_i$都是$2$的幂次。要求回答当$T=t_1,\ldots,t_m$的时候是否有解，其中$1\leq n,m\leq 10^6$。

类似题目1，这次我们在枚举的时候优先让球变成$2a_i$，如果不行才作为$a_i$使用，贪心解决。时间复杂度为$O(m\log_2M+n)$。