线性时间中的子集和

Question

这是我们算法期末考试的问题.这是逐字的,因为教授让我们把考试的副本带回家.

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

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

那么......这是一个棘手的问题吗？

---

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

Answer 1

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

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();
}

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