验证一个多集是否是另一个多集的子集和的并集

Question

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

详情如下：

多重集 A：正整数集

多重集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

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

4 一个数字的多个解决方案是可能的（如 7 可以是 1 和 6

，也可以是 3 和 4），但有些（如 7 可以是 1 和 6）在验证过程中可能是错误的。

5 多集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