3

我很难解决其中一个编程难题。我有一本字典，其中包含项目（用 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

有谁知道如何进行？使用哪种算法？

谢谢， 苏尼尔

4

1 回答 1

2

使用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

我把它留给你找到最便宜的合适组合:)

于 2012-11-29T18:40:35.990 回答