algorithm - 验证一个 multiset 是否是另一个 multiset 的子集和的并集

Question

我想找出一个算法来验证一个multiset是否是另一个multiset的子集和的并集，但是我自己奋斗了几个小时失败了。

详情如下:

Multiset A:一个正整数集

Multiset B:一个正整数集(小于等于A，后面你就会知道为什么)

算法功能:验证对于B中的所有数，A中的一个数或数之和是否匹配。 A中的每个数字只能使用一次，并且必须使用A中的所有数字。 B 中的所有数字必须匹配。

清除此问题的示例:假设多重集 A = {1, 3, 4, 4, 6} , B = {5, 6, 7}

然后算法将输出“TRUE”，因为 5 是 1 和 4 的和，6 等于 6，7 是 3 和 4 的和。同时 A 中的所有数字都被使用并且只使用一次，而B 中的所有数字都已检查。

但对于 A = {2, 6, 8}, B = {7, 9}，算法将输出“FALSE”，虽然 2+6+8 = 7+9，但 B 中的数字都不是A 中的数字。

一些注意事项:

1 已知条件，A中数之和等于B中数之和。

2 如示例所示，某个数字可以出现多次。

3 multiset 中的每个数字只能使用一次，因此如果在一个解决方案中使用了 3(得到 7)，则不能在另一个解决方案中再次使用它。数字 4 出现了两次，所以它可以用在两种解决方案中。

4 一个数的多个解是可能的，(比如 7 可以是 1 和 6，或者它可以是 3 和 4)，但是有些(比如 7 可以是 1 和 6)在验证过程中可能是错误的。

5 Multiset A不大，最多30个元素

我尽力而为，但我的解决方案始终无法涵盖多重集 A 和 B 的所有条件。我认为对此的解决方案显然超出了我的能力范围。

所以，我真的需要你们这些聪明人的帮助。请帮我。任何答案将不胜感激!

Answer 1

它是 NP 完全问题(还原为“子集和问题”非常简单)。所以这个问题没有有效的解决方案。

你可以在这里看到不同的解决方法: http://en.wikipedia.org/wiki/Subset_sum_problem

朴素算法:

naiveAlg(A,B) :
  for each partition P of A such that |P| = |B| do :
    for each element E in P do :
      calculate the sum of E numbers and store in E'
    if E' is equal to B return true
  return false