找到具有最大总和的n个数字的组合的算法

Question

问题很简单—— 假设我有一组以下数字 - 4,1,4,5,7,4,3,1,5 我必须找到可以从上面具有最大总和的数字创建的每组 k 个元素的数量。如果两组至少有一个不同的元素，则它们被认为是不同的。例如如果 k = 2，则可以有两个集合 - {7,5} 和 {7,5}。注意：5在上面的数组中出现了两次。

我想我可以从- 1.排序数组 2. 创建两个数组。一个用于不同的数字，另一个并行用于数字的出现。

但我现在卡住了。有什么建议么？

Answer 1

您可以执行以下操作：

1) 将元素降序排列；

2) 定义变量answer=1;

3) 从数组的开头开始，对于您看到的每个新值，计算它出现的次数（我们称此变量为计数）。每次做：答案=答案*计数。伪代码应该是这样的。

find_count(Array A, K)
{
   sort(A,'descending);
   int answer=1;
   int count=1;
   for (int i=1,j=1; i<K && j<A.length;j++)
   {
        if(A[i] != A[i-1])
        {
            answer = answer *count;
            i++;
            count=1;
        }
        else
            count++;
   }
      return answer;
}

Answer 2

我会创建一个排序字典，记录输入中数字的出现频率。然后取最大的两个数，乘以它们出现的次数。

在 C++ 中，它可能看起来像这样：

std::vector<int> inputs { 4, 1, 4, 5, 7, 3, 1, 5};
std::map<int, int> counts;

for (auto i : inputs) 
    ++counts[i];

auto last = counts.rbegin();

int largest_count = *last;
int second_count = *++last;

int set_count = largeest_count * second_count;

Answer 3

编辑： 我编辑了答案，因为我们发现 OP 需要计算多重集。

首先，找到数组中最大的 k 个数字。这当然很容易，如果 k 很小，您可以通过执行 k 线性扫描在 O(k) 中完成。如果 k 不是那么小，你可以使用二叉堆，或者优先级队列，或者只是对数组进行排序来完成排序时分别为 O(n * log(k)) 或 O(n * log(n)) 的操作。

假设您已经计算出 k 个最大的数字。当然，所有大小为 k 且总和最大的集合都必须恰好包含这些 k 最大的数字，而不能包含其他数字。另一方面，任何不同的集合都没有最大的总和。

设count[i]为数字i在输入序列中出现的次数。

设occ[i]为最大k个数中i的出现次数。

我们可以用非常不同的方式计算这两个 table，例如使用散列 table 或者如果输入数字很小，您可以使用由这些数字索引的数组。

设 B 为 distinct 个数与最大 k 个数的数组。设 m 为 B.

的大小

现在让我们计算答案。我们将分 m 步完成。在第 i 步之后，我们将计算出由 B 中的前 i 个数字组成的不同多重集的数量。一开始结果是 1 因为只有一个空的多重集。在第 i 步中，我们将当前结果乘以从 count[B[i]] 个元素中选择 occ[B[i]] 个元素的可能数量，等于 binomial(occ[i], count[i])

例如，让我们考虑在末尾再添加一个 7 并且 k 设置为 3 的实例：

k = 3

A = [4, 1, 4, 5, 7, 4, 3, 1, 5, 7]

A中最大的三个数是7, 7, 5

一开始我们有：

count[7] = 2
count[5] = 2
occ[7] = 2
occ[5] = 1
result = 1
B = [7, 5]

我们从 B 中的第一个元素开始，它是 7。它的 count 是 2，它的 occ 也是 2，所以我们做：

// binomial(2, 2) is 1
result = result * binomial(2, 2)

B中的下一个元素是5，它的count是2，它的occ是1，所以我们做：

// binomial(2, 1) is 2
result = result * binomial(2, 1)

最后的结果是2，因为有两个不同的多重集[7, 7, 5]

Answer 4

算法如下：

1) 按降序排列元素。

2) 看看这个数组。它可能看起来像这样：

   a ... a b ... b c ... c d ...
   |  <-    k   ->    |

现在显然所有元素 a 和 b 都将在总和最大的集合中。您不能用更小的元素替换它们中的任何一个，因为这样总和就不会是最大的。所以你在这里别无选择，你必须选择所有 a 和 b for any of the sets.

另一方面，只有一些元素 c 会出现在这些集合中。所以答案只是可能性的数量，选择 c 来填充集合中剩余的位置，在你采用 all 更大的元素之后。即二项式系数：

count of c's 选择 (k - (count of elements larger than c))

例如数组（已在此处排序）

[9, 8, 7, 7, 5, 5, 5, 5, 4, 4, 2, 2, 1, 1, 1]

和k = 6，你必须为每个总和最大的集合（即41）选择9、8和两个7。然后你可以从四个 5中选择任何两个。所以结果将是 4 choose 2 = 6.

使用相同的数组和 k = 4，结果将是 x choose 0 = 1（唯一的集合是 {9, 8, 7, 7}），使用 k = 7 结果将是 4 choose 3 = 4，并使用 k = 9：2 choose 1 = 2（为总和最大的集合选择任意 4 个）。

找到具有最大总和的n个数字的组合的算法

Algorithm to find combination of n numbers with largest sum

puzzle

algorithm