6

这是我们算法期末考试的一道题。这是逐字逐句的，因为教授让我们把考试副本带回家。

  1. （20 分）令 I = {r1,r2,...,rn} 是一组n 个任意正整数，并且I中的值是不同的。 我没有按任何排序顺序给出。假设我们想要找到I'的子集，使得I '中所有元素的总和正好是 100*ceil(n^.5) （ I 的每个元素最多可以在I'中出现一次）。提出一个 O( n ) 时间算法来解决这个问题。

据我所知，它基本上是背包问题的一个特例，也称为子集和问题......这两者都在 NP 中，理论上不可能在线性时间内解决？

那么......这是一个诡计问题吗？

这篇 SO 帖子基本上解释说，如果权重有界，则可以进行伪多项式（线性）时间近似，但在考试问题中，权重不受限制，无论哪种方式，考虑到考试的整体难度，我都会感到震惊如果教授希望我们知道/想出一个模糊的动态优化算法。

4

3 回答 3

4

有两件事使这个问题成为可能：

  1. 输入可以被截断为大小 O(sqrt(n))。没有负输入，因此您可以丢弃任何大于 100*sqrt(n) 的数字，并且所有输入都是不同的，因此我们知道最多有 100*sqrt(n) 输入很重要。
  2. 比赛场地的大小为 O(sqrt(n))。尽管有 O(2^sqrt(n)) 方法可以组合重要的 O(sqrt(n)) 输入，但您不必关心离开 100*sqrt(n) 范围或冗余命中的组合你已经可以达到的目标。

基本上，这个问题尖叫着动态编程，每个输入都以某种方式针对“到达数字”空间的每个部分进行检查。

解决方案最终是确保数字不会脱离自身（通过在正确的方向上扫描），只查看每个数字一次，并为我们自己提供足够的信息以在之后重建解决方案。

下面是一些应该在给定时间内解决问题的 C# 代码：

int[] FindSubsetToImpliedTarget(int[] inputs) {
    var target = 100*(int)Math.Ceiling(Math.Sqrt(inputs.Count));

    // build up how-X-was-reached table
    var reached = new int?[target+1];
    reached[0] = 0; // the empty set reaches 0
    foreach (var e in inputs) {
        // we go backwards to avoid reaching off of ourselves
        for (var i = target; i >= e; i--) {
            if (reached[i-e].HasValue) {
                reached[i] = e;
            }
        }
    }

    // was target even reached?
    if (!reached[target].HasValue) return null;

    // build result by back-tracking via the logged reached values
    var result = new List<int>();
    for (var i = target; reached[i] != 0; i -= reached[i].Value) {
        result.Add(reached[i].Value);
    }
    return result.ToArray();
}

我还没有实际测试过上面的代码，所以要小心拼写错误和错误。

于 2013-12-17T08:32:18.687 回答
2

用典型的DP算法解决子集和问题会得到O(N)耗时的算法。我们用dp[i][k](boolean) 来表示前 i 项是否有一个总和为 k 的子集，转移方程为：

dp[i][k] = (dp[i-1][k-v[i] || dp[i-1][k]),

其中O(NM)N 是集合的大小，M 是目标总和。由于元素是不同的并且总和必须等于100*ceil(n^.5)，我们只需要考虑最多前 100*ceil(n^.5) 个项目，然后我们得到N<=100*ceil(n^.5)和M = 100*ceil(n^.5)。

DP算法是O(N*M) = O(100*ceil(n^.5) * 100*ceil(n^.5)) = O(n).

于 2013-12-17T09:10:04.420 回答
1

好的，以下是 O(n) 时间内的简单解决方案。

由于所需的总和S是 的数量级O(n^0.5)，如果我们制定一个复杂度的算法S^2，那么我们很好，因为我们的算法应该具有有效的复杂度O(n)。

  1. 遍历所有元素并检查该值是否小于 S。如果是，则将其推送到新数组中。该数组应包含最多 S 个元素 (O(n^.5))

  2. 在 O(sqrt(n)*logn) 时间 (< O(n)) 中按降序对该数组进行排序。之所以如此，是因为 logn <= sqrt(n) 对于所有自然数。https://math.stackexchange.com/questions/65793/how-to-prove-log-n-leq-sqrt-n-over-natural-numbers

现在这个问题是一个一维背包问题，W = S，元素数 = S（上限）。

最大化物品的总重量，看看它是否等于 S。

它可以使用线性时间的动态规划来解决（线性 wrt W ~ S）。

于 2013-12-17T07:41:53.117 回答