所以，我想做的是在這里使用這兩個表，并從表1中得出一個組合，將表2的組合加起來的總數 1500或更少，但永遠不能低于表 2 500 的值。最后它應該回傳組合，稍后將在其余代碼中使用。
例如，假設我們想出了一個組合，并且這個組合使用了表 2 中的所有 4 個專案，我們可以使用所有這些專案，因為它符合限制條件，現在如果我們將表 2 中的所有值相加，您將得到 11,620。現在我們必須從表 1 中得出一個組合，其值至少為 12,120 但小于 13,120。
如果您需要有關我要在此處存檔的內容的更多詳細資訊，請告訴我！
限制
- 每個組合最多只能有 4 個專案
- 每個專案的值由“值”定義。
表 2
[
{
"UAID":143071570,
"assetId":19027209,
"name":"Perfectly Legitimate Business Hat",
"value":10549
},
{
"UAID":143334875,
"assetId":19027209,
"name":"Perfectly Legitimate Business Hat",
"value":10549
},
{
"UAID":1235149469,
"assetId":100425864,
"name":"Deluxe Game Headset",
"value":1795
},
{
"UAID":2756318596,
"assetId":20573078,
"name":"Shaggy",
"value":1565
},
{
"UAID":3499638196,
"assetId":20573078,
"name":"Shaggy",
"value":1565
},
{
"UAID":11002211144,
"assetId":102618797,
"name":"DJ Remix's Goldphones",
"value":7393
},
{
"UAID":50913661583,
"assetId":4390875496,
"name":"Diamond Crystal Circlet",
"value":4886
}
]
表 2
[
{
"UAID":672099668,
"assetId":60888284,
"name":"DarkAge Ninjas: Dual Kamas",
"value":4461
},
{
"UAID":6599510068,
"assetId":554663566,
"name":"Manicbot 10000",
"value":4319
},
{
"UAID":63414825508,
"assetId":91679217,
"name":"Sailing Hat",
"value":1886
},
{
"UAID":150428091864,
"assetId":8785277745,
"name":"Cincinnati Bengals Super Bowl LVI Helmet",
"value":954
}
]
uj5u.com熱心網友回復：
這是我多次展示過的技術，但似乎沒有其他人聽說過。
這個想法與尋找所有可能的數字組合以達到給定的總和相同，但更復雜，因為我們需要重復執行此操作。它是創建一個資料結構，從中可以輕松找到總和為特定值的子集。
class SubsetSumIter:
def __init__ (self, data):
self.data = data
# Build up an auxilliary data structure to find solutions.
last_index = {0: [-1]}
for i in range(len(data)):
for s in list(last_index.keys()):
new_s = s data[i]['value']
if new_s in last_index:
last_index[new_s].append(i)
else:
last_index[new_s] = [i]
self.last_index_by_target = last_index
self.targets = sorted(last_index.keys())
def subsets_at_target(self, target, max_i=None):
if max_i is None:
max_i = len(self.data)
for i in self.last_index_by_target[target]:
if i == -1:
yield [] # empty sum
elif max_i <= i:
break # went past our solutions
else:
for answer in self.subsets_at_target(target - self.data[i]["value"], i):
answer.append(self.data[i])
yield answer
def subsets_in_range(self, lower, upper):
i_min = 0
i_max = len(self.targets)
while 1 < i_max - i_min:
i_mid = (i_min i_max) // 2
if self.targets[i_mid] < lower:
i_min = i_mid
else:
i_max = i_mid
i = i_min 1
while i < len(self.targets) and self.targets[i] <= upper:
for answer in self.subsets_at_target(self.targets[i]):
yield answer
i = i 1
由此我們可以創建您想要的連接條件，如下所示：
def complex_join(table1, table2):
iter1 = SubsetSumIter(table1)
iter2 = SubsetSumIter(table2)
# For each sum from table2
for target in iter2.targets:
# For each combination from table 1 in our desired range
for subset1 in iter1.subsets_in_range(target 500, target 1500):
# For each combination from table 2 that gets that target
for subset2 in iter2.subsets_at_target(target):
yield (subset1, subset2)
并為您的示例找到所有 38 個解決方案：
t1 = [
{
"UAID":143071570,
"assetId":19027209,
"name":"Perfectly Legitimate Business Hat",
"value":10549
},
{
"UAID":143334875,
"assetId":19027209,
"name":"Perfectly Legitimate Business Hat",
"value":10549
},
{
"UAID":1235149469,
"assetId":100425864,
"name":"Deluxe Game Headset",
"value":1795
},
{
"UAID":2756318596,
"assetId":20573078,
"name":"Shaggy",
"value":1565
},
{
"UAID":3499638196,
"assetId":20573078,
"name":"Shaggy",
"value":1565
},
{
"UAID":11002211144,
"assetId":102618797,
"name":"DJ Remix's Goldphones",
"value":7393
},
{
"UAID":50913661583,
"assetId":4390875496,
"name":"Diamond Crystal Circlet",
"value":4886
}
]
t2 = [
{
"UAID":672099668,
"assetId":60888284,
"name":"DarkAge Ninjas: Dual Kamas",
"value":4461
},
{
"UAID":6599510068,
"assetId":554663566,
"name":"Manicbot 10000",
"value":4319
},
{
"UAID":63414825508,
"assetId":91679217,
"name":"Sailing Hat",
"value":1886
},
{
"UAID":150428091864,
"assetId":8785277745,
"name":"Cincinnati Bengals Super Bowl LVI Helmet",
"value":954
}
]
for answer in complex_join(t1, t2):
print(answer)
如果你想在最后得到一個（可能很大的）串列，你可以簡單地list(complex_join(t1, t2)).
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/464735.html