如何在预算内选购最多品类商品并使总价最接近预算？

给定店铺商品列表，需在预算内选购尽可能多品类的商品，且在满足品类数最多的前提下，总价要尽可能接近预算。需要实现函数maximize_products(budget, product_list)，输入预算与商品列表，返回符合要求的商品名称列表。

现有代码仅能实现选最多品类，但无法在同品类数的组合中筛选出总价最接近预算的组合，需要补充相关计算与比较逻辑。

示例输入：

budget = 3000, product_list = [("Apples", 1000), ("Banana", 500), ("Oranges", 1500), ("Grapes", 2000), ("Cherry", 800)]

示例输出：["Banana", "Apples", "Oranges"]（品类数3，总价刚好等于预算，是同品类数组合中最接近预算的）

现有代码：

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))

现有代码采用贪心策略：按价格从小到大依次选取商品，直到无法再加入下一个商品为止。这种方式能保证选到最多品类，但无法覆盖所有同品类数的组合。比如示例输入中，现有代码会选["Banana", "Cherry", "Apples"]（总价2300），但存在同品类数的组合["Banana", "Apples", "Oranges"]（总价3000），后者总价更接近预算，显然更符合需求。

我们可以用动态规划来记录每个品类数对应的最大总价，以及对应的商品组合，从而在保证品类数最多的前提下，找到总价最接近预算的组合。

修改后的代码：

def maximize_products(budget, product_list):
    # 动态规划数组：dp[k] 存储两个值 (最大总价, 对应的商品名称列表)
    # k表示选取的商品品类数
    max_possible_count = len(product_list)
    dp = [(-1, []) for _ in range(max_possible_count + 1)]
    dp[0] = (0, [])  # 选0个商品时总价0，空列表

    for name, price in product_list:
        # 倒序遍历品类数，避免重复选取同一个商品
        for k in range(max_possible_count, 0, -1):
            prev_total, prev_list = dp[k-1]
            if prev_total != -1 and prev_total + price <= budget:
                # 如果当前组合的总价比已记录的k品类组合总价更高，就更新
                if prev_total + price > dp[k][0]:
                    new_list = prev_list.copy()
                    new_list.append(name)
                    dp[k] = (prev_total + price, new_list)

    # 找到最大的品类数k，且对应的总价有效
    max_k = 0
    for k in range(max_possible_count, -1, -1):
        if dp[k][0] != -1:
            max_k = k
            break

    # 返回该k对应的商品列表
    return dp[max_k][1]

# 输入部分保留
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))

1. 动态规划数组初始化：dp[k]存储选k个商品时的最大总价和对应的商品列表，初始时只有选0个商品的状态是有效的（总价0，空列表）。
2. 遍历商品更新状态：对每个商品，倒序遍历品类数k，避免重复选同一个商品。如果选k-1个商品的状态有效，且加上当前商品价格不超预算，同时总价比当前k品类的记录更高，就更新dp[k]。
3. 找到最优解：从最大可能的品类数倒序查找，找到第一个有效的状态（即能选到k个商品），对应的商品列表就是满足最多品类且总价最接近预算的组合。

测试示例输入时，该代码会返回["Banana", "Apples", "Oranges"]，符合预期。

内容的提问来源于stack exchange，提问作者yhc