组合解决这个难题？

以下是来自Coderbyte“简单”部分的练习。组合解决这个难题？

函数ArrayAdditionI（arr）取数组数组并返回“true”，如果数组中的任何数字组合可以加到等于数组中最大的数字，否则返回“false”。例如：如果arr包含[4,6,23,10,1,3]，则输出应该返回true，因为4 + 6 + 10 + 3 = 23。

我可以想象一个交互式解决方案，但复杂性使我惊慌失措。我需要去研究解决这个问题？

我正在阅读组合函数C（n，k）。这是正确的道路吗？

来源

2013-08-21 dwilbank

这应该有助于http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a -given-sum – elclanrs

观看斯坦福讲座。只是想确保他们肯定会申请。谢谢。 – dwilbank

我认为这是一个1d装箱或knappsack问题。这个问题也是一个决策问题，所以这是一个NP问题。它可能是一个弱多项式问题。

来源

2013-08-21 21:55:30 Bytemain

-1

有可能是一个很天真的解决方案：

arrAddition = function(values) { 
    // sort from largest 
    values.sort(function(a, b) { 
     return b-a; 
    }); 
    var sum = 0; 
    // starts from second, and add until reaching the limit 
    for (var i = 1; i < values.length; i++) { 
     sum += values[i]; 
     if (sum == values[0]) { 
      return true; 
     } else if (sum > values[0]) { 
      // don't go further 
      return false; 
     } 
    } 
    // or fail. 
    return false 
}

它甚至与Underscore方便的方法（如减少）短。

但我可能会完全误解了问题...

来源

2013-08-21 21:57:33 Feugy

你好我相信跳过某些组合 – dwilbank

的确，它只找到一种组合！但是这就是你要求的：有没有组合。优点是它非常快速：一次排序，另一次查找解决方案。乐观的情况下，你可能会阻止第三个元素！复杂度：O（n） – Feugy

如果组合超过它，这将返回true。它适用于所有剩余元素完全合并到最大元素而不超过它的示例。它不适用于以下情况：10,9,8。它应该返回false，因为9 + 8超过10，但会返回true。您可以将> =改为==，但需要添加额外的逻辑以允许无序组合。例如。 10，6，5，4.将6和5一起添加会导致它超过10并失败，但该组数字应该返回true（6 + 4）。好开始。 – Kate

组合解决这个难题？

回答

相关问题