performance - 子集和的变体

Question

我通读了所有子集求和主题，但在实现以下问题的算法时仍然遇到问题。

给定 N 个整数 (N<=20) 的数组 A，其中

• a[i]<=20
• 值不必是唯一的

和一个整数 K (K<=20)。

规则:

• 等于 K 的数组项被 K“覆盖”。
• 如果两个或多个数组数字之和等于K，则这些数字也被覆盖。
• 数组中的每个数字只能覆盖一次。

示例:

N=6，整数:1、1、2、3、4、5

K=4

可能的覆盖范围:

1. 报道
   • 4 被覆盖。
   • 1, 1, 2 被覆盖为 1+1+2=4。
2. 报道
   • 4 已覆盖。
   • 1, 3 被覆盖为 1+3=4。

K=5

可能的覆盖范围:

1. 报道
   • 5 个已覆盖。
   • 1,1,3 被覆盖为 1+1+3=5。
2. 报道
   • 5 个已覆盖。
   • 1,4 被覆盖为 1+4=5。
   • 2,3 被覆盖为 2+3=5。

目标:

对于给定的数组 A 和整数 K，找到所有可能的“覆盖范围”。我需要所有覆盖范围，而不仅仅是覆盖大部分数组项的覆盖范围。

我尝试了两种方法:

1. 蛮力算法。检查所有可能大小的所有可能子集是可行的，但即使只有 10 个数字也会花费太多时间。我需要它在不超过 500 毫秒内完成。
2. 首先，我按降序对数组进行排序。然后，对于每个可能的子和数，我创建“插槽”。我循环遍历数组并按照以下规则将数字放入插槽中:
   • 如果数字之和等于 K，则将数字放入槽中。
   • 将数字放在所有槽中总和最小的槽中。
   • 将数字放入槽中，它给出所有槽中的 K 个最接近的总和。

好吧，第二种方法行之有效，而且速度很快。但是我发现了一些没有找到覆盖范围的场景。

如果有人提供解决此问题的想法，我将不胜感激。

希望我能很好地解释问题。

谢谢。

Answer 1

我没有现成的答案，但我建议看一下“装箱问题”，它在这里可能会有用。

主要问题是找到所有可能的和给出数字 K。所以试试这个:

Collection All_Possible_Sums_GivingK;

find_All_Sums_Equal_To_K(Integer K, Array A)
{
    /* this function after finding result
    add it to global Collection AllPossibleSumsGivingK; */
    find_All_Elements_Equal_To_K(Integer K, Array A); 

    Array B = Remove_Elements_Geater_Or_Equal_To_K(Integer K, Array A);

    for all a in A {
        find_All_Sums_Equal_To_K(Integer K-a, Array B-a) 
    }
}