組合解決這個難題？

以下是來自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

組合解決這個難題？

回答

相關問題