使用給定的整數數組達到目標總和的算法，以避免某些數字？

這個練習是一個簡單具有挑戰性的Java程序。輸入包含：使用給定的整數數組達到目標總和的算法，以避免某些數字？

大小的陣列的「n」的，
用於陣列A中的輸入和
爲大小的另一個數組B中的輸入「N-1」
「finalsum」是陣列A中所有元素的總和

什麼是最正確的算法，用於打印添加數組A中所有元素以達到最終和的正確順序，即「finalsum」，從而避免求和達到排列B中的任何值。

Inputs: (split to three lines for clarity) 

1. 

3    //n, the size of the array 
2 4 6   //array a of size n 
4 8   //array b of size n-1 

//finalsum = 2 + 4 + 6 = 12. Similarly for the 2nd input 

Output: 0 1 2 (or) 2 1 0 is also correct 
     but 1 0 2 is wrong because it cannot add up to 4, since 4 is present in the array b 

2. 

20 
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 

Output: 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 (or) many other ways too

來源

2013-10-16 s_iyer

這是一個家庭作業問題嗎？ – mellamokb

這是一個裝箱問題。看看它。 –

我試圖解決這個問題，它適用於某些輸入，但是它會給其他輸入提供ArrayIndexOutOfBoundsException錯誤，我不理解清除該錯誤所需的條件。 –

你的算法可以是這個樣子：

採取元素從A
添加元素，目前的總和。檢查電流和被包含在B
如果電流之和爲B，跳到下一個元素在A
如果目前的金額不得在B，遞歸從A選擇下一個元素（當前元素去掉）。
如果選擇了A中的所有元素，則返回索引作爲解決方案備份堆棧。
如果A的所有元素都經過測試而沒有解決方案，和我們目前處於遞歸堆棧的最頂層，那麼結論就是沒有解決方案。

大多數這些步驟應該相對簡單的實施。

來源

2013-10-16 19:34:11 mellamokb

以稍微不同的方式嘗試這個方法，即通過查看數組的設置並對其執行設置操作。僅適用於某些輸入，而其他一些輸入則提供arrayindexoutofBounds異常。 –

那麼你正在嘗試訪問數組範圍外的數組索引:)你是否嘗試過在你的IDE中使用調試器來查看它究竟發生了什麼？當你的意思是「A」時，你有可能在某處意外地提到了'B'，因爲它們的大小相差1？或者你的設置邏輯中可能存在一個邏輯錯誤，或者是一個偏離1的索引錯誤？有很多原因，但它將在代碼中，而不是算法。 – mellamokb

好吧，按照你的邏輯，如果在遞歸過程中的某個時刻，A中的所有值加上「當前總和」後給出的值存在於B中，那麼我們不能再簡單地跳過，因爲不會在A中添加任何更多元素以添加到「當前總和」中，該部分將生成ArrayIndexOutOfBounds異常。此外，在這種情況下，它並不一定意味着沒有可用的訂單，這只是錯誤的，而是程序試圖生成的訂單錯誤，但每個輸入仍然有一些正確的順序給予限制。 –

爲什麼我們不能使用所有置換算法的修改形式，其中檢查每個步驟中的總和。如果當前總和等於B中的任何元素（爲此我們可以使用散列圖），那麼不要繼續其他操作。

希望我清楚。

謝謝。

來源

2013-10-16 19:42:33 Trying

程序必須遵循一種總是返回好順序而不是測試每個排列的算法，這是構建程序的條件之一。而且，輸入可以最多不超過100個，所以測試每個組合將會非常緩慢，這不是預期的。 –

@Suraj'返回一個很好的順序，而不是測試每個排列'在這裏你的好順序是什麼意思？我認爲你需要所有的數字排列，其中沒有中間和等於B中的任何數字。 – Trying

使用給定的整數數組達到目標總和的算法，以避免某些數字？

回答

相關問題