從python字典優化輸出

Question

我有很難解決編程難題之一。我有一個字典，其中有物品（用i＃表示）和價值作爲該物品的價格。「物品可以組合形成組合包。

{('i2', 'i3'): '4', ('i1',): '1',('i1', 'i3', 'i4'): '6.5', ('i3',): '3',('i1', 'i2', 'i3'): '4.5', ('i2',): '2', ('i4',): '4'} 

我想返回給定輸入項目的最低價格。用戶不會有任何問題，如果他得到額外的項目在最低價格從組合包：

1. 對於輸入I1，它應該返回的價格1（這是所有I1項目的最低價格）
2. 對於輸入（ I1，I2），應該返回3.
3. 對於輸入（I1，I2，I3，I4），應該返回8.5
4. 對於輸入（I1，I1，I2，I3，I4），應該返回9.5

有沒有人有任何想法如何繼續下去？使用哪種算法？

感謝， 蘇尼爾

Answer 1

使用itertools.combinations()產生X包的組合。然後，檢查每個組合是否包含所需項目，並查找具有最低價格的有效組合。

要查找的4個不同項目的包所有組合：

d = {('i2', 'i3'): '4', ('i1',): '1',('i1', 'i3', 'i4'): '6.5', ('i3',): '3', 
    ('i1', 'i2', 'i3'): '4.5', ('i2',): '2', ('i4',): '4'} 
from itertools import combinations 
combos = list(combinations(d, 4)) # you should try combos of different lenghts, 
            # from 1 to the number of desired items 

爲了說明，讓我們來看看連擊之一。 print combos[0]給出：
(('i2', 'i3'), ('i1',), ('i1', 'i3', 'i4'), ('i3',))

而得到這個組合的價格：

sum([float(d[item]) for item in combos[0]]) 

其中給出14.5

我讓你找到最便宜的合適組合:)