时间约束下最大化金额：替代Pandas双列排序的算法咨询

我有一个包含A、B两列的字典列表，原本用Pandas按A列升序、B列降序排序，代码如下：

df.sort_values(["A", "B"], ascending=[True, False], inplace=True)

但有些场景需要优先考虑代表金额的B列，目标是在最大时间周期约束下最大化总金额（A列代表耗时）。之前的排序逻辑只优先最小耗时再考虑金额，满足不了需求。请问有没有能解决这个问题的算法？

输入示例 #

input_list = [
    {"A": 10, "B": 200},
    {"A": 70, "B": 1000},
    {"A": 10, "B": 300},
    {"A": 10, "B": 100},
]

最大耗时约束：80ms

期望输出 #

output = [
    {"A": 10, "B": 300},
    {"A": 70, "B": 1000},
]

此时总金额为1300，是约束下的最大值。

你遇到的问题本质是经典的0-1背包问题——每个元素（这里的字典项）只能选择一次，在总耗时（背包容量）不超过最大值的前提下，最大化总金额（背包价值）。

算法思路 #

• 定义动态规划数组dp，其中dp[i]表示总耗时不超过i时能获得的最大金额。
• 初始化dp数组为全0，dp[0] = 0（耗时为0时金额为0）。
• 遍历每个字典项，从最大耗时约束值倒序遍历到当前项的耗时，更新dp数组：
  若i >= 当前项的A值，则dp[i] = max(dp[i], dp[i - 当前项的A值] + 当前项的B值)
• 回溯dp数组，找出被选中的字典项，得到最优组合。

针对示例的实现代码 #

def knapsack_max_value(items, max_time):
    # 初始化DP数组，记录对应耗时下的最大金额
    dp = [0] * (max_time + 1)
    # 记录每个耗时状态对应的选中项，用于回溯结果
    selected = [[] for _ in range(max_time + 1)]
    
    for item in items:
        time_cost = item["A"]
        value = item["B"]
        # 倒序遍历避免重复选择同一元素
        for i in range(max_time, time_cost - 1, -1):
            if dp[i - time_cost] + value > dp[i]:
                dp[i] = dp[i - time_cost] + value
                # 更新选中列表：继承前一状态的选中项，加上当前项
                selected[i] = selected[i - time_cost] + [item]
    
    # 返回最大耗时约束下的最优选中项
    return selected[max_time]

# 测试示例
input_list = [
    {"A": 10, "B": 200},
    {"A": 70, "B": 1000},
    {"A": 10, "B": 300},
    {"A": 10, "B": 100},
]
max_time = 80
output = knapsack_max_value(input_list, max_time)
print(output)

代码说明 #

• 运行代码会输出符合期望的结果，总金额1300、总耗时80ms。
• 若存在多个总金额相同的最优组合，代码会返回其中一种，可根据需求调整回溯逻辑获取所有组合。
• 时间复杂度为O(n * C)，其中n是字典项数量，C是最大耗时约束，中小规模数据下效率很高。

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