如何用Python实现预算分配最大化下载量的算法？

你的初始代码存在关键局限——它只能从给定选项中挑选单个投放方案，完全忽略了可以通过组合多个不同金额的投放选项利用剩余预算，进而获得更高下载量。比如预算35000时，最优解应该是「10k付费搜索（1000下载）+20k付费搜索（2000下载）」，总下载量3000，但你的代码会选中「30k付费搜索（2500下载）」，显然不是最优结果。

这个问题本质是0-1背包问题：我们需要在给定预算内，选择若干不可重复的投放选项，让总下载量最大。下面是基于动态规划的优化实现：

def maximize_downloads(budget, options):
    # 初始化DP数组：dp[i]表示预算为i时的最大下载量
    dp = [0] * (budget + 1)
    
    # 遍历每个投放选项
    for cost, downloads in options:
        # 倒序遍历预算，避免重复选择同一个选项
        for current_budget in range(budget, cost - 1, -1):
            # 更新当前预算下的最大下载量：选或不选当前选项
            dp[current_budget] = max(dp[current_budget], dp[current_budget - cost] + downloads)
    
    # 回溯找到最优组合的选项（若只需要最大下载量，可省略此部分）
    remaining_budget = budget
    best_combination = []
    for cost, downloads in reversed(options):
        if remaining_budget >= cost and dp[remaining_budget] == dp[remaining_budget - cost] + downloads:
            best_combination.append((cost, downloads))
            remaining_budget -= cost
    
    # 返回最优组合和最大下载量
    return best_combination, dp[budget]

# 投放选项：(成本, 下载量)，前半为展示广告，后半为付费搜索
options = [
    (10000, 500), (10000, 1000),
    (20000, 900), (20000, 2000),
    (30000, 1200), (30000, 2500),
    (40000, 1450), (40000, 2700),
    (50000, 1600), (50000, 2850)
]

budget = 35000
best_combination, max_downloads = maximize_downloads(budget, options)

print(f"最优组合：{best_combination}，总下载量：{max_downloads}")

代码关键点说明 #

• DP数组设计：dp[current_budget]存储预算为current_budget时的最大下载量，初始值全为0（预算为0时无下载）。
• 倒序遍历预算：确保每个投放选项仅被选择一次，避免重复选取同一档位的投放。
• 回溯过程：如果需要明确知道选中了哪些投放选项，可通过回溯DP数组得到最优组合；若只需要最大下载量，这部分可以直接省略。

测试结果 #

当预算为35000时，代码输出：最优组合：[(20000, 2000), (10000, 1000)]，总下载量：3000，这是当前预算下的最优解。

内容的提问来源于stack exchange，提问作者Anton Hulan-Gioro