k个元素不大于m的最大的一笔 [英] Largest sum of k elements not larger than m

问题描述

此问题是由一个编程比赛，我不能设法解决它在可接受的时间。

This problem is from a programing competition, and I can't manage to solve it in acceptable time.

您将得到一个数组的 A N 整数。找到最大的一笔取值究竟 K 元素（不一定是连续的），不超过一个给定的整数 M（S＆LT;米）。

You are given an array a of n integers. Find the largest sum s of exactly k elements (not necessarily continuous) that does not exceed a given integer m (s < m).

约束：

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

信息：A溶液是保证存在给定输入

Info: A solution is guaranteed to exist for the given input.

现在，我想我最好的选择是一个DP的办法，但不能拿出正确的公式。

Now, I guess my best bet is a DP approach, but couldn't come up with the correct formula.

推荐答案

我将要做两件事情。它们都基于以下想法：

I would try two things. They are both based on the following idea:

如果我们能够解决决定的问题，如果有 K 元素之和完全到 P ，那么我们就可以在 [1，M] 。

If we can solve the problem of deciding if there are k elements that sum exactly to p, then we can binary search for the answer in [1, m].

1。优化的暴力破解

简单排序阵列和削减你的搜索总之当电流总和超过 P 。我们的想法是，你通常只需要原路返回很少，因为排序后的数组将有助于及早消除不良的解决方案。

Simply sort your array and cut your search short when the current sum exceeds p. The idea is that you will generally only have to backtrack very little, since the sorted array should help eliminate bad solutions early.

说实话，我怀疑这将是速度不够快，但是。

To be honest, I doubt this will be fast enough however.

2。随机算法

请尺寸 K 的用阵列。随机指定的元素给它。虽然他们的总和不 P ，随机替换元素与另一并确保更新它们的和在固定时间内。

Keep a used array of size k. Randomly assign elements to it. While their sum is not p, randomly replace an element with another and make sure to update their sum in constant time.

请这样做的最大电子商务倍（实验，其最佳效果的价值，复杂度将是 0（E M）的到底，所以它也许可以去相当高），如果你不能得到总结 P 在此期间，假定它是不可能的。

Keep doing this a maximum of e times (experiment with its value for best results, the complexity will be O(e log m) in the end, so it can probably go quite high), if you couldn't get to sum p during this time, assume that it is not possible.

另外，忘记了二进制搜索。直接运行随机算法，并返回找到的最大的一笔有效的电子运行，或者直到你分配的运行时间结束。

Alternatively, forget the binary search. Run the randomized algorithm directly and return the largest valid sum it finds in e runs or until your allocated running time ends.

我不知道怎么DP将有效地跟踪在款项使用的元素的数量。我认为，随机算法是值得一试，因为它很容易实现。

I am not sure how DP would efficiently keep track of the number of elements used in the sum. I think the randomized algorithm is worth a shot since it is easy to implement.

这篇关于k个元素不大于m的最大的一笔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！