组合算法

Question

组合算法

algorithmmathcombinatorics

12

我遇到了一个有趣的编程问题，但似乎无法找到解决方案。假设你有K个球，颜色各不相同，你必须将所有的球划分成尽可能多的组，使得没有两个组是相同的（如果两个组每种颜色的球的数量相同，则认为它们是相同的）。你最多可以划分成多少组？

约束条件： 1<=K<=50， 1<=N<=14

澄清一下：我们需要一个算法，接受由整数组成的数组作为输入，其中每个整数>=1。数组的大小为N，它包含的值的总和为K。该算法应返回最大组数。

对于这个问题，有什么算法方法吗？

- TheDarBear

2

看起来 K 是你的瓶颈，所以让 N=14。然后你有一个空集合组，14个单色组，18个双色组，这就是你的极限了。 - jsheeran

1

@ScottMermelstein 这个问题是我的一位教授提出来的，他也在尝试解决它。 - TheDarBear

3

“K个不同颜色的球中”是指您总共有K个球吗？还是您总共有K*N个球？ - Jim Mischel

3

有K个球，N种不同的颜色，但我们不知道每种颜色有多少个球？ - Jim Mischel

1

引理：对于N >= K+2，存在一个包含K个大小为1的组（每种颜色一个）的最优解。假设G是给定K和N的最优组集。假设c是我们的K种颜色之一，并且在G的任何大小为1的组中都没有出现。找到G中包含颜色c的球的任何组X。将c移动到它自己的组中。现在，我们知道X - c与G中的另一个组相同，因为G是最大的。将X - c的球移动到剩余组中最大的组中（我们知道该组的大小>= 2，因此不会减少单球组的数量）。 - Dave

显示剩余23条评论

3个回答

1

在与我的教授再次交谈后，我了解到这是开放式kattis.com 问题的适应版本。

两者几乎相同，因为原问题的任何实例都可以通过对N进行质因数分解并将每个质因数视为球来解决。例如，900 = 2^2*3^2*5*2，因此等效的球问题将是2 2 2。

给定的范围是使用10^15的最大范围找到的。 2^50 > 10^15，因此永远不可能有超过50个因素，并且将前15个质数相乘也将超过10^15，这意味着最多只能有14组。

然而，我认为忽略了球数和组数之间的权衡，这使得问题更容易解决。例如，如果有14个组，则每个组中只有1个球，而如果有50个球，则它们都属于同一组（这是由于原始问题的10^15约束所导致的）

有了这些新信息，我成功地解决了问题。我将N分解为质数列表和所有因子的列表，然后使用多维背包算法（如果N有X个唯一的质因子，则背包DP将是X+1维，其中第一维表示您正在考虑哪个项目，每个其他维度代表您剩余某个质因子的供应量）。 N的每个因子都可以代表一个可能放入背包中的物品，其质因数分解是其成本向量。

做完这些后，最大情况下问题仍然太慢，需要进行额外的优化。我发现存在一种最佳解决方案，即尽可能使用单球组。通过在开始时创建尽可能多的1球组并解决剩余的子问题，我能够在Kattis的时间限制内完成问题。

我的算法依赖于我已经证明的两个假设：

如果你可以不使用所有的球来制作X组，则也可以使用所有的球来制作X组。这使得背包问题的解决方案中，不使用100%容量的情况是有效的。通过将所有未使用的球添加到最大的一组中，可以证明这个假设。这将创建一个比任何其他组都大的组，因此它必须是唯一的。这样，您就可以保持相同数量的组，但所有球都被利用。
始终存在一种使用尽可能多的单球组的最优解。这使得原始问题可以缩小为在时间限制内可解决的子问题。这也可以被证明。取任何最优解。对于不存在的任何1球分组，请取包含该1球的组，并将该组中的每个其他球移动到最大的组中。这将创建一个具有相同（最优）组数的解决方案，其中尽可能多地使用了1球组。

我的解决方案的运行时间为O(F(N)^2)，其中F(N)是N的因子总数。

- TheDarBear

感谢您回来解释。我并没有接近解决方案，而且我现在没有太多时间。顺便问一下，您能否发布一个输入和结果列表，以便那些想出有效算法的人可以检查他们的结果？ - m69 ''snarky and unwelcoming''

10的15次方也包含在这个问题陈述中吗？如果是，您能否将其编辑到问题中，以便此答案更有意义？如果它与此问题无关，而只与您链接的那个问题有关，为什么要在这里包含它？ - Bernhard Barker

1

我会从K个单元素组开始，逐步完善它们，直到所有组都不同。在每一步中，我们移除两个组，将它们合并并放回新的组。难点在于选择哪些组，我建议按以下因素排序选择（按重要性降序排列）：

更多不同结果胜出（例如，两个组合并成一个新的不同组，胜过两个组合并成已知组）
较小的结果胜出（例如，两个元素组胜过三个元素组）
最常见的组合

我不确定当有多个选择时，需要强制尝试所有组合，还是采取任何路径都会导致最优解，但当我们需要尝试多个组合时，动态规划方法将是必要的，以限制状态爆炸。

示例（每行按出现次数排序）：

b  g-g-g  r-r-r-r  m-m-m-m-m  y-y-y-y-y-y-y  c-c-c-c-c-c-c-c-c-c
b  cc  g-g-g  r-r-r-r  m-m-m-m-m  y-y-y-y-y-y-y  c-c-c-c-c-c-c-c
b  cc  cy  g-g-g  r-r-r-r  m-m-m-m-m  y-y-y-y-y-y  c-c-c-c-c-c-c
b  cc  cy  cm  g-g-g  r-r-r-r  m-m-m-m  y-y-y-y-y-y  c-c-c-c-c-c
b  cc  cy  cm  yy  g-g-g  r-r-r-r  m-m-m-m  y-y-y-y  c-c-c-c-c-c
b  cc  cy  cm  yy  cr  g-g-g  r-r-r  m-m-m-m  y-y-y-y  c-c-c-c-c
b  cc  cy  cm  yy  cr  cg  g-g  r-r-r  m-m-m-m  y-y-y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  g-g  r-r-r  m-m-m  y-y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  rm  g-g  r-r  m-m  y-y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  rm  g  yg  r-r  m-m  y-y  c-c-c-c
b  cc  cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m-m  c-c-c-c
b  cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m-m  cc-cc  c-c
b  cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m  cc  mcc  c-c
cy  cm  yy  cr  cg  my  rm  g  yg  r  y  ry  m  cc  mcc  c  cb

g-g-g  r-r-r-r-r  b-b-b-b-b
rb  g-g-g  r-r-r-r  b-b-b-b
rb  rg  g-g  r-r-r  b-b-b-b
rb  rg  br  g  r-r-r  b-b-b
rb  rg  br  g  r  rr  b-b-b
rb  rg  br  g  r  rr  b  bb

作为一个算法的每一步，我没有生成所有可能的组合来删除并按上面的比较函数排序，而是向后走以获得一些候选者：

1.选择最常见的组并删除一个，然后选择（现在）最常见的组并删除一个 2.查看它们一起是否有比更少的常见组可以实现的更多元素 3.查看它们是否组合成一个未知组 4.如果是，则采取它们，如果不是，则从下一个常见组开始重复步骤1

这基本上询问以下问题：

1.这个组（元素的组合）有多常见/它的出现次数是多少？ 2.是否已经生成了该组中元素的所有可能组合，且大小低于某个特定值？ 3.是否已经生成了该组元素和下一组元素的所有可能组合？

它们的结果可以以动态编程的方式缓存，以便我们可以快速跳过一些候选项（直到真的没有好的选择，并且我们必须执行合并以不生成新的不同组，如上例中行变短时所示）。我们还可以假设我们基本上永远不会选择仅出现一次的组，因为这将被认为不会生成具有更多不同组的结果。

- Bergi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- m69 ''snarky and unwelcoming'' · Accepted Answer

我将假设输入的格式为：

(我一直在试图制定游戏策略，但是我遇到了反例，所以我重新编写了答案，只保留那些似乎有效的部分。)

输入

我将假设输入的格式为：

{K:30, N:6, red:4, green:3, blue:1, cyan:10, magenta:5, yellow:7}

这也可以写成：

rrrr ggg b cccccccccc mmmmm yyyyyyy

单球组

首先观察到一个单球只能将一个无效（重复）组转化为一个有效（唯一）组，因此如果不使用单球来形成单球组，则只能获得一个组，所以最好开始创建每种可用颜色的单球组。

r g gg ggg (ggg) = 4  
  g gg ggg rggg  = 4

r g b bb bbb bbbbbb     = 6
r g b bb bbb bbbb (bb)  = 6
    b bb bbb bbbb rb gb = 6

这实际上将具有K个N种颜色的输入转换为具有K-N个N种或更少颜色的问题，最大为49:1、48:2……36:14。上述例子从30:6减少到了24:5。

rrrr ggg b cccccccccc mmmmm yyyyyyy  
r g b c m y  +  rrr gg ccccccccc mmmm yyyyyy

小到大的分组

如果在转移到 S+1 大小之前尽可能创建多个 S 大小的组，并且你有 S 个未使用的球，它们将形成一个重复的 S 大小的组，但如果有一种方法可以避免这种情况，那么你将拥有一个额外的 S 大小的组，这意味着 S 大小的组的解决方案一开始并不是最优的。

如果在转移到 S+1 大小之前尽可能创建多个 S 大小的组，并且你有超过 S 个未使用的球，那么你用它们形成的更大的组永远不会重复 S 大小的组。

从这个结论中很容易假设创建单球组，然后 2 球组，然后 3 球组 ... 将导致最优解。然而，有些情况下并非如此：

{K:45, N:5, red:3, green:3, blue:3, cyan:3, yellow:33}  
rrr ggg bbb ccc yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

r g b c y                         =  5  
rg bc ry gy by cy yy              =  7  
yyy yyyy yyyyy yyyyyy yyyyyyy (y) =  5
                            TOTAL = 17

r g b c y                         =  5  
      ry gy by cy yy              =  5  
ryy gyy byy cyy                   =  4  
yyy yyyy yyyyy yyyyyy             =  4  
                            TOTAL = 18

看起来这就是50个球最大数量的限制所在。如果你首先制作尽可能多的1个球组，然后是2、3……，有可能你必须拆分一个较小的组，将剩余的球（或一个独特的组+剩余的球）转化为两个或更多个独特的组。然而，似乎无法改进没有剩余球的解决方案，至少在这个输入大小限制下。

找到最佳的2人小组数量意味着填充一个类似于这样的二维表：

   r  g  b  c  m  y
r  +
g  +  -
b  +  -  +
c  -  +  -  -
m  +  +  -  +  +
y  -  +  +  -  -  +

可能存在1 + 2 + ... + N个可能的组合，但这并不意味着有2 ^ (1 + 2 + ... + N)种选择需要考虑。一方面，我们正在寻找最佳解决方案，因此没有必要查看仅有少数组合的解决方案；另一方面，在制作了1球组后，最多还剩下K - N个球可用于制作组合。还有一件事是，某些颜色可能没有N + 1个球，因此不能同时制作该颜色的所有组合；实际上，使用超过6种颜色时，无法创建所有2球组合：

 N   K-N   pairs  combi

 1    49    24      1
 2    48    24      3
 3    47    23      6
 4    46    23     10
 5    45    22     15
 6    44    22     21
 7    43    21     28
 8    42    21     36
 9    41    20     45
10    40    20     55
11    39    19     66
12    38    19     78
13    37    18     91
14    36    18    105