algorithm - 按总项目限制分组集

问题描述

我有一组物品：{1}, {2}, {2,3}, {13,7}, {7,2,18}. 和限制（项目=> 最大项目数）：（count(1)<=10, count(2)<=2, count(3)<=5, count(7)<=1, count(13)<=10, count(18)<=10不超过，总共不超过 22个）。我需要找到适合限制的初始集合的最佳子集。例如，{2}, {2,3}, {7,2,18}不适合，因为它总共有 32个，但 limit 只有 2 个2。

内部集合是不可变的，例如{7,2,18}不能拆分。内套可以是任何尺寸（但实际上它们大约是 1-5 件）

就我而言，“最佳”的定义有点模糊。我对一个拥有最多集合的子集没意见。或一个子集，其中包含最多的项目。

目前，我有这个（对于“一个具有最多集合的子集”的情况）：

计算每个项目的当前总数（{1=>1, 2=>3, 3=>1, 7=>2, 13=>1, 18=>1}
查找受限制 ( {2, 7})影响的项目
查找包含受影响项目的集合 ( {2}, {2,3}, {13,7}, {7,2,18})
生成这个较小集合的所有子集（2^4、16 个子集，包括空的）
计算每个子集的限制
停止匹配的第一个子集

我的问题：我不确定我的解决方案是否是最优的，并且它具有指数级的复杂性。

有更好的解决方案吗？

（在实践中，这是一种罕见的情况，该项目达到限制）

标签： algorithm

解决方案

对您来说代价高昂的步骤是计算集合集的所有分区，以从限制的角度查看哪些分区是有效的。您正在生成一个 O(2^n) 树（其中 n 是初始子集的数量），然后查看所有叶子。

您可以通过首先搜索更有希望的候选人并在达到（最佳）解决方案时立即停止来显着加快这一速度。例如，为了“具有最多集合的子集是最好的”目标，您可以使用以下伪代码：

place initial state (= set with all subsets) S in queue Q 
do
   pop first state from Q
   if valid, return it: it is an optimal answer
      else,
         for each subset I in the current state S
             push state S-I (that is, that does not include subset I) to Q
while Q is not empty
if this line is reached, return "no answer possible"

请注意，在最坏的情况下（= 没有可能的答案），这与您以前的情况一样糟糕。但是如果要删除的子集很少，这将在 O(2^r) 中找到它们，其中r是需要删除以达到最佳答案的最小子集数。

如果您避免重新访问状态，则可以进一步加快思考速度：r将达到具有已删除子集的（无效）状态的2^r次数。但是请注意，这是一个时空权衡：访问状态缓存越大，您需要的内存就越多。

其他优化也是可能的，例如用于选择首先删除哪些子集的启发式方法；例如，包含当前超出其限制的项目的子集应优先于不包含此类项目的子集。

algorithm - 按总项目限制分组集

问题描述

解决方案

推荐阅读