python - Python 中允许多个项目的简化 0/1 背包问题

Question

我有一个问题是背包问题的简化版本。它是这样的。有一家商店，我们有该商店的商品清单。比方说，商店有两种类型的产品普通产品和限量产品。

产品类别

class Product:
    """ 
    A class to provide abstraction for products availabel in the system.
    unless the product is a Limited_product its supply is infinite
    """
    product_counter = 0

    ##### Part 1.1 #####
    def __init__(self, name, price):
        """ Constructor for initialization """
        
        self.name = name
        self.price = price
        self.id = Product.product_counter
        Product.product_counter += 1

    def __str__(self):
        """ returns a string representation of a product """
        return "<{}> {} - {}$".format(self.id, self.name, self.price)

    def __repr__(self):
        """ represents the class object as a string """
        return "PRODUCT <{}>".format(self.id)

有限的产品类别

class Limited_Product(Product):
    """
    A child class of the parent Product class
    Represents a Limited product where the quantity is depreceating
    """

    ##### Part 1.2 #####
    def __init__(self, name, price, amount):
        """ Constructor for initialization """
        super().__init__(name, price)
        self.amount = amount

    def __str__(self):
        """ returns a string representation of a limited product """
        return "<{}> {} - {}$ ({} left)".format(self.id, self.name, self.price, self.amount)

    def decrement_amount(self):
        """ decrement the amount of available product """
        self.amount -= 1

    def get_amount(self):
        """ returns the amount available from the product """
        return self.amount

现在我们得到了一个产品列表和客户可以花费的最大金额。

==============================

产品 - 价格

一个 - 20 美元

乙 - 7 美元

C - 1 美元（剩下 2 个）

==============================

我们必须通过递归和迭代完成给定的两个函数来找出客户从这些项目中购买序列后剩余的最小金额。给出了这些函数，所以我不能用不同的方法编写。

举个例子：

>>> store.so_rich(45)

output - 1

你有 45 美元可以花。最佳解决方案是购买 6 件 B 品和 2 件 C 品。这将使您剩下 45 - 7 * 6 - 1 * 2 = 1 美元。剩下的最少钱是 1，因为没有办法花掉所有的钱。（虽然 C 的价格是 1 美元，但您已经全部购买了！）

>>> store.so_rich(61)

0

你有 61 美元可以花。您可以通过购买两个 A 和三个 B (20 * 2 + 7 * 3 = 61) 来花费所有这些。所以剩下的最少钱是0。

我写的两个函数

    def so_rich(self, money):

        # suppose you haven't seen any product yet
        # the only possible amount of money left is "money"
        # this is a set to record the possible money left
        left = set([money])

        # get products
        lst = list(self.warehouse.inventory.values())
        print(str(lst))
        for product in lst:

            # a temporary set to save the updates of "left"
            # you don't want to modify the set you're iterating through
            tmp_left = set()

            for m in left:
                # update tmp_left
                if type(product) != Limited_Product:
                    new_left = m
                    #new_left -= product.price
                    while product.price <= new_left:
                        print(new_left, product.name)
                        tmp_left.add(new_left)
                        new_left = new_left - product.price
                else:
                    # handle limited product
                    new_left = m
                    product_count = product.amount
                    while product.price <= new_left and product_count > 0:
                        print(new_left, product.name)
                        tmp_left.add(new_left)
                        new_left = new_left - product.price
                        product_count -= 1
            left = tmp_left
            print(left)

        return min(left)

    def so_rich_recursive(self, money):

        # get products
        lst = list(self.warehouse.inventory.values())
        
        def helper(lst, money):
            
            # base case
            if not lst:
                return money
            
            cur_min = money
            product = lst[0]
            if type(product) != Limited_Product:
                tmp = money
                while product.price < tmp:
                    cur_min = tmp
                    tmp -= product.price
                    print(cur_min, product.name)
            else:
                tmp = money
                product_count = product.amount
                while product.price <= tmp and product_count > 0:
                    cur_min = tmp
                    tmp -= product.price
                    product_count -= 1
                    print(cur_min, product.name)
            money = money - cur_min
            print("-----", money)
            lst.pop(0)
            return helper(lst, money)
        
        return helper(lst, money)

我无法理解为什么我编写的上述代码不起作用。任何人都可以帮助我吗？

标签： pythonpython-3.xlistrecursionknapsack-problem