號碼添加到一個特定的許多Java

-1

什麼是最有效的方式來檢查，如果陣列中的任何數字總結到特定號碼，例如：的（5,3,3,9,4）我的數組想知道這些數字中的任何數字是否可以添加到給出的10 這會發生在我添加時（3,3,4）號碼添加到一個特定的許多Java

這裏有一個關於此的線程：http://stackoverflow.com/questions/15532957/to-find-a-subset-from-a-set-whose-sum-equals-to-zero – user2147970

你已經描述了[子集總和問題]（http://en.wikipedia.org/wiki/Subset_sum_problem） –

你只有正數嗎？ –

我將不得不花更多的時間比我現在上來有一個非常好的解決方案，但我會建議重新考慮你的策略。正如@DeepakBala提到的，你正在描述一個NP完全問題。

一兩件事，使這個不同的是，和（Q）可以比陣列中的數字顯著大。另外，由於它們限制在3到150之間，所以當你有2000個號碼時，你將會有很多重複。充分利用這些優勢 - 在使用這些數字之前對數字進行計數，並且您只需要擔心149種類型的數字。

爲了讓你思考爲什麼的問題，考慮排序百萬的數字1-100。只需創建一個數組，然後計算您看到每個數字的次數。然後通過將每個數字打印出合適的次數來重新創建列表。這是O（n）而不是正常的O（n log（n））。

，而不是與達2000個數字數組，可考慮150陣列是告訴你你有多少可用的每個大小和多少你正在使用的每個大小。

嘗試將所有的大數，直到你中的Q 150，然後，如果您有任何完美補足差額看到。如果失敗了，你必須弄清楚如何從那裏出發。

2013-04-15 17:58:37

謝謝對於你的幫助，但我沒有得到你提到的觀點：「嘗試添加所有的大數字，直到你在150的Q內，然後看看你是否有任何完美彌補差異。」 – user2283297

例如，如果你有150場的10場，149場的9場和148場的11場，給你4469.如果Q是4600，那麼你檢查你是否有一個大小爲4600-4469 = 131的場。 –

回答