情况: 您将获得商店中销售的产品列表,并且您希望在给定的预算(最接近给定的预算)内购买尽可能多类型的产品。编写函数“最大化产品(预算,产品列表)”,该函数将预算和产品列表作为输入,并返回尽可能多的可购买产品的列表。返回的清单应仅包含您要购买的产品名称,并且应在不超出预算的情况下包含尽可能多的品种。
输入示例: 预算 = 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))
如何添加计算和比较产品价格总和的功能?
这是一个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]