我有大量具有定義順序的數字。簡單來說，邏輯如下所示：
資料['值'] = [1,1,3,4,4,-9,10]
資料['訂單'] = [1,2,3,4,5,6,7]
預期總和 = 0
我希望回傳的是在總和等于 0 的情況下我們可以獲得的最大可能值子集的原始順序和值。對于這種情況，一個最佳解決方案是
解決方案['值'] = [1,1,3,4,-9]
解決方案['order'] = [1,2,3,4,6]
也可以通過將 4 階數替換為 5 階數來實作總和，但是，一個最佳解決方案就足夠了。目標是達到總和 = 0 的子集的最大可能大小。
正在尋找背包問題和最大子陣列演算法的變體，但沒有一個能滿足我的需求。
任何提示或方向表示贊賞。
uj5u.com熱心網友回復：
可以使用“n 選擇 k”方式找到所有固定長度的子集。為了找到最長的迭代，迭代從 k=n 開始并減一。
import itertools as it
def combination_finder(l: list) -> tuple:
for i in range(len(l)):
for pair in it.combinations(enumerate(l), len(l)-i):
i, c = zip(*pair)
if sum(c) == 0:
return (i, c)
raise Exception('No combination found.')
l = [1,1,3,4,4,-9,10]
id_, comb = combination_finder(l)
print(id_)
print(comb)
備注：id要從1開始，只需更改enumerate如下enumerate(l, start=1)
uj5u.com熱心網友回復：
也許我遺漏了一些東西（已經很晚了），但是如果我們用k元素表示一個子集，S(k)并且我們N總共有元素，你可以：
- 看看
S(N)總和是否為0；如果是這樣，那是最大的子集 - 如果不是，請查看是否有任何
S(N-1)總和為 0；有N這樣的集合 - 如果沒有，看看是否有任何一個
S(N-2)；有N*(N-1)這樣的集合
等等。這是一個“蠻力”解決方案，可能遠非最佳，但如果預計最大的子集相對較大（接近N大小），它應該不會太糟糕。請注意，每個步驟都可以利用上一步中計算的總和。
您solution[order]似乎是解決方案子集的索引。當然可以，但我不確定為什么需要同時獲取值和它們的索引？這有點多余。
最后，雖然在純 Python 中可行，但 NumPy 庫可能對這類問題有用。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/466277.html
上一篇：以編程方式設計自定義表格視圖單元