如何在给定预算（最接近给定预算）内购买尽可能多类型的产品

Question

情况： 您将获得商店中销售的产品列表，并且您希望在给定的预算（最接近给定的预算）内购买尽可能多类型的产品。编写函数“最大化产品（预算，产品列表）”，该函数将预算和产品列表作为输入，并返回尽可能多的可购买产品的列表。返回的清单应仅包含您要购买的产品名称，并且应在不超出预算的情况下包含尽可能多的品种。

输入示例： 预算 = 3000，product_list = [("苹果"，1000)，("香蕉"，500)，("橙子"，1500)，("葡萄"，2000)，("樱桃"，800)]

示例输出： [“香蕉”、“苹果”、“橙子”]

我能够包含尽可能多的品种，但我很难获得成本最接近给定预算的产品组合。请帮忙...

def maximize_products(budget, product_list):

    sorted_products = sorted(product_list, key=lambda x: x[1])

    selected_products = []
    total_cost = 0

    for product, price in sorted_products:
        if total_cost + price <= budget:
            total_cost += price
            selected_products.append(product)
        else:
            break

    return selected_products

budget=int(input("budget: "))
product_list=[]
n = int(input("number of products: "))

for i in range(n):
    name, price=input("Enter the product name and price (ex: apple 1000): ").split()
    product_list.append((name, int(price)))


print(maximize_products(budget, product_list))

如何添加计算和比较产品价格总和的功能？

Answer 1

这是一个0/1背包问题，可以使用动态规划来解决。

解决方案说明

• 1。初始化变量： 创建一个大小为

  dp

  的二维数组

  (n+1) x (budget+1)

  ，其中

  n

  是列表中产品的数量。每个位置

  dp[i][j]

  代表使用第一个

  i

  产品和预算

  j

  可以实现的最大总成本。

• 2。要构建 DP 表： 从 1 到给定预算迭代每个产品和每个可能的预算。对于每种产品

  i

  和预算

  j

  ，有两种选择：
  • 如果当前产品的价格小于或等于当前预算，则包含当前产品。在这种情况下，最大总成本是两个选项中的最大值：
    • 不包括当前产品

      (dp[i-1][j])

      ，或
    • 包括当前产品并按当前产品的价格减少预算

      (dp[i-1][j - product_list[i-1][1]] + product_list[i-1][1])

      。
  • 如果当前产品的价格超出当前预算，则排除当前产品。在这种情况下，最大总成本保持与上一行相同

    (dp[i-1][j])

    。

• 3。查找产品组合： 从表格的最后一个单元格回溯，重建导致总成本最大的产品组合。从最后一个单元格

  (dp[n][budget])

  开始向后移动。如果

  dp[i][j]

  的值与

  dp[i-1][j]

  不同，则表示组合中包含第i个产品。将产品名称添加到组合列表中，并将

  j

  更新为

  j - product_list[i-1][1]

  。继续这个过程直到得到第一个产品。

解决方案

def maximize_products(budget, product_list):
    # Initialize variables
    n = len(product_list)
    dp = [[0] * (budget + 1) for _ in range(n + 1)]

    # Build DP table
    for i in range(1, n + 1):
        for j in range(1, budget + 1):
            if product_list[i - 1][1] <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - product_list[i - 1][1]] + product_list[i - 1][1])
            else:
                dp[i][j] = dp[i - 1][j]

    # Find the combination of products
    combination = []
    j = budget
    for i in range(n, 0, -1):
        if dp[i][j] != dp[i - 1][j]:
            combination.append(product_list[i - 1][0])
            j -= product_list[i - 1][1]

    return combination[::-1]