号的一个子集的总和 [英] Sum of a subset of numbers

问题描述

说我有一个数字N和数字表。我想选择多达四个表中的数字，并且这四个总和将是最接近的可能匹配到n。给定表中的长度L，组合它要经过数为（6 * L + 11 * L ^ 2 + 6 * L ^ 3 + L ^ 4）/ 24

Say I have one number 'n' and a table of numbers. I want to choose up to four of the numbers in the table, and the sum of those four will be the closest possible match to n. Given length 'L' of the table, the number of combinations it has to go through is (6*L + 11*L^2 + 6*L^3 + L^4)/24.

恩。说我有变量

n = 100

和该组数字中

t = {86, 23, 19, 8, 42, 12, 49}

鉴于此列表中，四个至n最接近组合是49 + 23 + 19 + 8 = 99

Given this list, the closest combination of four to n is 49 + 23 + 19 + 8 = 99.

什么是计算尽可能少的数量这样做的最佳方法是什么？

What is the optimal way of doing this with the least possible number of calculations?

推荐答案

这看起来像子集和'的变化（见的 http://en.wikipedia.org/wiki/Subset_sum_problem ），这是众所周知的是NP完全问题，所以很遗憾很可能不会有任何聪明算法在所有，在最坏情况下将运行任何越快指数中的项数。

This looks like a variation of the 'subset sum' (see: http://en.wikipedia.org/wiki/Subset_sum_problem) problem which is known to to be NP complete, so unfortunately most probably there won't be any clever algorithm at all that in the worst-case will run any faster that exponential in the number of items.

在的情况下不会有太多的项目检查（东西约10个左右），您可以尝试的深度优先搜索剪枝尽快。

In case there are not many items to check (something about 10 or so) you might try a depth first search pruning branches as soon as possible.

如果有很多更多的项目来检查寻找最佳的解决方案，你可以更好地试图找到一个稍微好逼近最有可能代替。

If there are a lot more items to check most probably instead of searching for the optimal solution you might better try to find a somewhat good approximation.

这篇关于号的一个子集的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！