查找

Question

我已經寫了一個邏輯找到位置可用數量字典中的相對量， 的位置和數量與字典管理：

d={'loc2': 500.0, 'loc3': 200.0, 'loc1': 1000.0, 'loc4': 100.0, 'loc5': 50.0} 

from operator import itemgetter 
def find_combination(locs,qty): 
    locs = sorted(locs.items(),key=itemgetter(1),reverse=True) 
    result = [] 
    for loc,val in locs: 
     if qty <= 0: 
      break 
     elif qty - val >= 0: 
      qty -= val 
      result.append((loc,val)) 
    return result 

現在，當量變的最大數量如下該字典它給這些意想不到的結果：

print find_combination(d,1000) 
[('loc1', 1000.0)] 
print find_combination(d,750) 
[('loc2', 500.0), ('loc3', 200.0), ('loc5', 50.0)] 
print find_combination(d,1900) 
[('loc1', 1000.0), ('loc2', 500.0), ('loc3', 200.0), ('loc4', 100.0), ('loc5', 50.0)] 
print find_combination(d,150) 
[('loc4', 100.0), ('loc5', 50.0)] 
print find_combination(d,34) 
[] # unexpected # should be [('loc5', 50.0)] 
print find_combination(d,88) 
[('loc5', 50.0)] # should be [('loc4', 100.0)] 

Answer 1

您可以創建一個字典使用dictionray鍵一次存儲所有可能的組合，這將給：

d={'loc2': 500.0, 'loc3': 200.0, 'loc1': 1000.0, 'loc4': 100.0, 'loc5': 50.0} 
from itertools import combinations 
comb = {} 
for i in range(1,len(d)): 
    [comb.__setitem__(sum(j),k) for k,j in zip(combinations(d.keys() ,i), 
               combinations(d.values(),i))] 

的comb字典是這樣的：

{50.0: ('loc5',), 
100.0: ('loc4',), 
150.0: ('loc4', 'loc5'), 
200.0: ('loc3',), 
250.0: ('loc3', 'loc5'), 
300.0: ('loc3', 'loc4'), 
350.0: ('loc3', 'loc4', 'loc5'), 
500.0: ('loc2',), 
550.0: ('loc2', 'loc5'), 
600.0: ('loc2', 'loc4'), 
650.0: ('loc2', 'loc4', 'loc5'), 
700.0: ('loc2', 'loc3'), 
750.0: ('loc2', 'loc3', 'loc5'), 
800.0: ('loc2', 'loc3', 'loc4'), 
850.0: ('loc2', 'loc3', 'loc4', 'loc5'), 
1000.0: ('loc1',), 
1050.0: ('loc1', 'loc5'), 
1100.0: ('loc1', 'loc4'), 
1150.0: ('loc1', 'loc4', 'loc5'), 
1200.0: ('loc3', 'loc1'), 
1250.0: ('loc3', 'loc1', 'loc5'), 
1300.0: ('loc3', 'loc1', 'loc4'), 
1350.0: ('loc3', 'loc1', 'loc4', 'loc5'), 
1500.0: ('loc2', 'loc1'), 
1550.0: ('loc2', 'loc1', 'loc5'), 
1600.0: ('loc2', 'loc1', 'loc4'), 
1650.0: ('loc2', 'loc1', 'loc4', 'loc5'), 
1700.0: ('loc2', 'loc3', 'loc1'), 
1750.0: ('loc2', 'loc3', 'loc1', 'loc5'), 
1800.0: ('loc2', 'loc3', 'loc1', 'loc4')} 

然後，您可以建立一個功能chekc如果給定的組合存在：

find_combination = lambda num: comb.get(num, 'NOT A VALID COMBINATION') 

例子：

find_combination(1750) 
#('loc2', 'loc3', 'loc1', 'loc5') 

find_combination(1): 
#'NOT A VALID COMBINATION' 

---

編輯：如果你的字典變得太大，最好是使用基於迭代器這個功能：

def find_combination(d, num): 
    from itertools import combinations,izip 
    t = ((sum(j),k) for i in range(1,len(d)) \ 
        for j,k in izip(combinations(d.values(),i), 
            combinations(d.keys() ,i))) 
    for comb,k in t: 
     if comb==num: return k 

Answer 2

我不能完全肯定，如果你的算法是一個你需要的。如果想法是從不同的位置獲得一定的數量，那麼你的算法將找不到最佳的組合，只是一個好的組合。

您的問題可以被看作是一個0-1 knapsack problem可以在僞多項式時間內解決使用Dynamic Programming

Answer 3

這怎麼是一個意想不到的結果？

當qty = 34和val = 50,qty - val >= 0將評估爲false。

到qty = 88和val = 100

程序的結果聽起來不錯，我:)

在一個側面說明情況類似：

def find_combination(locs,qty): 
    locs = sorted(d.items(),key=itemgetter(1),reverse=True) 

但我猜你的意思是locs = sorted(locs.items(), ...