algorithm - 不大于 m 的 k 个元素的最大和

Question

这个问题来自编程竞赛，我无法在可接受的时间内解决它。

给你一个数组 a的 n整数。找出最大的总和 s恰好 k不超过给定整数的元素(不一定是连续的)m (s < m) .

约束:

 0 < k <= n < 100
 m < 3000
 0 < a[i] < 100

信息:对于给定的输入，保证存在一个解决方案。

现在，我想我最好的选择是 DP 方法，但无法得出正确的公式。

Answer 1

我会尝试两件事。它们都基于以下想法:

如果我们可以解决确定是否有 k 个元素恰好 和 p 的问题，那么我们可以二分查找在 [1, m] 中回答。

<强>1。优化的暴力破解

当当前总和超过 p 时，简单地对数组进行排序并缩短搜索时间。这个想法是你通常只需要很少的回溯，因为排序的数组应该有助于尽早消除不好的解决方案。

老实说，我怀疑这是否足够快。

<强>2。一种随机算法

保留一个大小为 k 的 used 数组。随机分配元素给它。虽然它们的总和不是 p，但随机将一个元素替换为另一个元素并确保在恒定时间内更新它们的总和。

继续这样做最多 e 次(用它的值进行实验以获得最佳结果，最终复杂度将是 O(e log m)，所以它可能会很高)，如果您无法在这段时间内对 p 求和，则假设这是不可能的。

或者，忘记二分查找。直接运行随机算法并返回它在 e 运行中找到的最大有效总和，或者直到您分配的运行时间结束。

我不确定 DP 如何有效地跟踪求和中使用的元素数量。我认为随机算法值得一试，因为它易于实现。