5

我有一个菜单 dict 项目作为键和价格作为值。可能存在比单个项目便宜一点的项目组合。例如：

menu = {
    ('burger',) : 5.00,
    ('pizza',) : 12.00,
    ('coke',) : 4.00,
    ('macpuff',) : 4.00,
    ('pasta',) : 3.00,
    ('french_fries',) : 2.00,
    ('burger', 'coke', 'french_fries') : 10.00,
    ('pizza', 'coke') : 15.00,
}

现在假设我订购了一些物品，那么输出将是给定订单的最小数量：

I/P >  burger, coke 
O/P >  9      (5.00 + 4.00) 

I/P >  burger, coke, french_fries
O/P >  10.00 

I/P >  pizza, coke, french_fries
O/P >  17.00    (15.00 + 2.00)

这是我尝试的所有价格的代码，我将用作生成器：

def isSubset(a, b):
    """
        compare two iterable and return true if first is subset of second
    """
    b = list(b)
    if not hasattr(a, '__iter__'):
        a = [a]
    for each in a: 
        try:
            b.remove(each)
        except ValueError:
            return False
    return True

def rest_min_price(order):
    if order:
        for item, price in menu.iteritems():
            if isSubset(order[0], item):
                new_order = order[1:]
                for itm in item:
                    try:
                        new_order.remove(itm)
                    except ValueError:
                        pass
                yield price + rest_min_price(new_order)

但是当我运行它时它说类型错误：

for each in rest_min_price(order_item):
    print each

TypeError: unsupported operand type(s) for +: 'int' and 'generator'
4

3 回答 3

5

谢谢大家的回复。我在某处使用了你的建议，现在我已经用不同的实现方法用相同的方法解决了它。

这是我的代码：

class Rest_Menu():
    def __init__(self, menu):
        self.menu = menu
        self.all_price = [] 

    def min_price(self, order, total_price=0):
        """
        Return minm menu price by calculating all possible combination.
        """
        if order:
            for item, price in self.menu.iteritems():
                if isSubset(order[0], item):
                    new_order = [each for each in order]
                    for itm in item:
                        try:
                            new_order.remove(itm)
                        except ValueError:
                            pass
                    self.min_price(new_order, price+total_price)
        else:
            self.all_price.append(total_price)
        return min(self.all_price)

再次感谢。:)

于 2014-01-03T05:36:42.650 回答
2

你误会了yield。一个包含的函数yield神奇地变成了一个生成器。如果你只是调用它，你会得到一个不能直接使用的生成器对象；您需要调用它的next()方法来从中提取值。大多数情况下，您将其放入for循环中。

>>> def genDemo(n):
...   while n > 0:
...     yield n
...     n -= 1
... 
>>> 
>>> gd = genDemo(3)
>>> gd
<generator object genDemo at 0x7fce12152820>
>>> gd.next()
3
>>> gd.next()
2
>>> gd.next()
1
>>> gd.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>> for x in genDemo(3):
...   print x
... 
3
2
1
>>> _

您的代码只是一个普通的递归函数；它可以使用return.

当您不想在内存中获取整个序列时，生成器很方便；对于非常长且无限的序列，它最有意义。您可以生成排列直到找到所需的排列，或者生成随机数直到找到所需的排列，或者从套接字读取直到收到退出消息，等等。

关于子集：除非您的数据以相同的方式排序，否则您不能懒惰地检查子集。使用您拥有的数据集，您最好使用内置的set.

于 2014-01-02T10:24:41.430 回答
0

您的问题在于您尝试将生成器与递归结合起来：

yield price + rest_min_price(new_order)

这里price是 a int，但是rest_min_price()是 a generator（因为你yield，而不是return它的结果），因此你不能将它们加在一起并得到 a TypeError。

您需要遍历生成器中的项目：

for item in rest_min_price(order_item):
    # process the item
    # yield result with price
于 2014-01-02T10:21:29.387 回答