1

我想找出一个算法来验证一个多重集是否是另一个多重集的子集和的并集，但是我自己挣扎了几个小时后失败了。

详情如下：

多重集 A：正整数集

Multiset B：一个正整数集（小于等于A，后面你会知道为什么）

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

一个澄清这一点的例子：假设 multiset A = {1, 3, 4, 4, 6} , B = {5, 6, 7}

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

但是对于A = {2, 6, 8}, B = {7, 9}，算法会输出“FALSE”，虽然2+6+8 = 7+9，但是B中没有一个数字是A中的数字之和.

一些注意事项：

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

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

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

4 一个数字有多种解法是可能的，（比如 7 可以是 1 和 6，也可以是 3 和 4），但有些（比如 7 可以是 1 和 6）在验证过程中可能是错误的。

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

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

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

4

1 回答 1

2

这是 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
于 2012-08-06T17:20:45.567 回答