我最近遇到了一個子集求和問題。我之前能夠使用 Java 為較小的陣列解決它，但在這種情況下，我真的不知道我該怎么辦。蠻力和重復可能不是一種選擇，因為我遇到了記憶體不足的問題。
所以，假設我們有一個{2500, 3200, 3300}陣列。我們正在尋找最接近所需數字 K = 135000的總和。主要區別在于我們可以多次使用陣列中的數字。
好的，如果我們可以多次使用它們，那么我們可以將其更改為更“傳統”的方式——只需將 K 除以這些數字中的每一個——即54、42 和 40——并創建一個新陣列，其中包含這些數字從除法中獲得的次數。它將是{2500, 2500, 2500, ... , ... 3300, 3300}并且新陣列的長度為 136。現在這遠不止 3。
那么 - 如何解決最接近的子集和問題，我們可以使用 Java從136 個或更多元素的陣列中選擇2 個以上的數字？
我想要得到的不僅是最接近的總和，而且是給出該總和的元素串列。
我聽說并正在閱讀有關動態規劃、近似演算法和遺傳演算法的資訊，但不幸的是我對這些一無所知。前段時間我做了一個不同情況的遺傳演算法，但我不確定在這種情況下如何使用它。
有任何想法嗎？我會很高興得到幫助。
uj5u.com熱心網友回復：
我不打算為你解決。但我會用偽代碼（又名 Python）為您提供關鍵思想。
我們從代表以下陳述句的狀態開始：“我不知道如何到達任何數字。best我可以生成的是0。我還沒有處理我可以到達的事實0。”
在資料中：
can_generate = set()
todo = [0]
best = 0
K = 135000
我們要做的是，當任何東西都在 中時todo，取出一個值，看看它對我們來說是否是新的。如果是，我們可能會更新best，并可能向 中添加新值todo。像這樣：
while len(todo):
value = todo.pop()
if value not in can_generate:
can_generate.add(value)
if abs(K-value) < abs(K-best):
best = value
if value < K:
for term in [2500, 3200, 3300]:
todo.append(value term)
現在我們知道 中的值can_generate，我們向后搜索以找到如何到達那里。
answer = []
while 0 < best:
for term in [3300, 3200, 2500]:
if best - term in can_generate:
answer.append(term)
best -= term
break
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/380289.html