algorithm - 在大于给定数字的数字列表中找到最佳元素总和

Question

我有一个数字列表，降序排列，数组的大小是可变的，可以出现任何数字(通常小于 1000)

给定一个输入数字 (x)，我需要在列表中找到值的最佳组合，即比 x 大可能的最小值。我一直在阅读有关 NP 优化和求和子集类型的问题，但还没有找到解决方案。我找到了一些近似算法的伪代码，但我想从给定的数字列表中找到确切的最优解。谢谢

Answer 1

根据您的评论，我了解到输入数组具有无符号(整数)。

这个问题好像和subset sum problem with non-negative integers没有太大区别|可以在多项式时间内求解。

我发现这是一个性能相当不错的算法，可以找到最优解:

伪代码中的算法

For each element of the array:
    select this element  
    if sum of selected <= x:
        # Sum is too small, so add more (smaller) term(s)
        execute algorithm recursively for the remaining part of array
    else if < sum in best solution so far:
        # Sum is closer to target, so this is currently the best
        best solution = current selected terms
    # Back-track: remove this term from the sum
    unselect this element
return best solutiuon

当递归调用算法时，先前选择的术语保持选中状态，并且在循环中再选择一个术语。可以再次递归等。选择的词条总数对应递归的深度。

递归有两种方式可以削减很多组合:

• 选择高值(value)项时，跨目标值的剩余值变得相对较小，从而减少了其他项可以促成(更好)解决方案的可能性；
• 选择较低的值项时，剩余的项数相对较小(由于订单)，因此可能性减少了。

这表明时间复杂度小于 O(2ⁿ)，这将是必须研究所有可能组合(或常数)时的复杂度它的一小部分)。

实现

这是一个 JavaScript 实现，您可以运行它。它提供了一个随机化按钮，因此您可以使用随机数和随机目标值生成任意给定长度的数组。

该算法似乎 以O(n.logn) 时间的顺序运行，只需查看它检查的平均组合数。这当然不是证明。

代码中的注释应该给出说明。

// Main  algorithm
function solve(a /* array of int */, x /* int */) {
    // Initialise
    var best = {sum: a[0] * a.length, numSumsVerified: 0, numTerms: 0, terms: []};
    var current = {sum: 0, terms: []};

    function recurse(start) {
        var ok = start < a.length;
        for (var i = start; i < a.length && best.sum > x + 1 && ok; i++) {
            // Use this term for the sum
            current.sum += current.terms[current.terms.length] = a[i];
            // Keep statistics of how many combinations we check
            best.numSumsVerified++;
            if (current.sum <= x) {
                // Sum is too small, so add more (smaller) term(s)
                ok = recurse(i+1);
            } else if (current.sum < best.sum) {
                // Sum is closer to target, so this is currently the best
                best.sum = current.sum;
                best.terms = current.terms.slice(0);
            }
            // Back-track: remove this term from the sum
            current.sum -= current.terms.pop();
        }
        return ok || i > start + 1;
    }

    // start the search, and capture errors
    try {
        recurse(0);
    } catch (ex) {
        best.error = 'Too much recursion!';
        best.sum = null;
        return best;
    }
    best.numTerms = best.terms.length;
    // if no solution, set error message
    if (!best.terms.length) {
        best.error = 'no solution';
        best.sum = null;
    }
    return best;
}

// Utility for randomizing
function createRandomNumbers(limit, count) {
    res = [];
    while (count--) res.push(Math.floor(Math.random() * limit));
    return res;
}

// I/O

var inputA = document.querySelector('#a');
var inputX = document.querySelector('#x');
var buttonSolve = document.querySelector('#solve');
var inputSize = document.querySelector('#size');
var buttonRandom = document.querySelector('#randomize');
var output = document.querySelector('pre');

buttonSolve.onclick = function() {
    // Get input
    var a = inputA.value.match(/\d+/g).map(Number);
    var x = Number(inputX.value);
    // Sort descending
    a.sort(function(a,b) { return b-a; });
    // Solve
    var result = solve(a, x);
    // Output
    inputA.value = a.join(' '); // just for reformatting
        // Reduce detail when many items
    if (result.terms.length > 100) result.terms = '(too many to display)';
    output.textContent = JSON.stringify(result, null, 4);
};

buttonRandom.onclick = function() {
    // Generate random input
    var size = Number(inputSize.value);
    var limit = size * 20;
    var a = createRandomNumbers(limit, size).sort((a,b) => b-a);
    var sum = a.reduce((a,b) => a+b);
    var x = createRandomNumbers(sum, 1).pop();
    // Populate the input boxes
    inputA.value = a.join(' ');
    inputX.value = x;
    // Trigger click on "solve" button
    setTimeout(buttonSolve.click.bind(buttonSolve), 0);
}

Enter list of integers: <input id="a" size="50" value="18 13 12 10 9 8 6 6 1 0"><br>
Sum must be larger than: <input id="x" size="10" value="16"><br>
<button id="solve">Solve</button><br>
Desired array size: <input id="size" size="6" value="50">
<button id="randomize">Random Input</button>
<pre></pre>

由于此算法对添加到组合中的每个项执行递归调用，因此对于大型输入数组，递归可能会深入。在某个时候它可能会达到堆栈限制。在我的浏览器中，该限制经常在接近 10,000 个元素的数组大小时受到影响。如果需要将此算法用于如此大的数组，可能可以在不使用递归的情况下重写该算法。