代码测试需求：给定重量限制下实现包裹成本最大化

嘿，这是经典0-1背包的一个小变种，我来给你捋清楚怎么实现，完美匹配你的需求～

核心需求拆解 #

咱们要解决的问题是：给定带编号、重量、成本的物品，还有包裹重量上限，选一组物品满足：

• 总重量 ≤ 包裹限制；
• 第一优先级：总成本尽可能大；
• 第二优先级：如果多组方案成本相同，选总重量最小的那个。

这比普通0-1背包多了一层优先级判断，所以得在动态规划的状态里兼顾这两个指标。

动态规划思路 #

我推荐用动态规划来搞，核心是维护一个dp数组，其中dp[w]表示“使用重量w时能达到的最大成本”。不过因为要处理成本相同选重量小的情况，咱们需要：

• 对于每个可能的重量，只保留最大的成本值；
• 当多个重量对应同一个最大成本时，咱们最后找那个最小的重量就行（这样组合更优）。

具体步骤走一遍：

1. 初始化：dp[0] = 0（重量为0时，成本自然是0），其他位置初始成-1（表示这个重量状态不可达）。另外整个prev数组，用来记录每个状态是从哪个重量、选了哪个物品过来的，方便后面回溯找选中的物品。
2. 遍历物品：对每个物品，从后往前遍历重量（这是0-1背包的常规操作，防止同一个物品被重复选），从包裹最大重量到当前物品的重量。
3. 状态更新：计算如果选当前物品的话，新的重量和成本。如果新成本比当前记录的大，直接更新；如果成本相等，先不用急着处理，等最后找最优解的时候再筛选最小重量。
4. 找最优解：先找出dp数组里的最大成本，然后在所有达到这个成本的重量里挑最小的那个，最后回溯找出对应的物品。

代码示例（Python） #

假设输入是物品列表，每个物品包含index（编号）、weight（重量）、cost（成本），还有包裹的最大重量max_weight。

def knapsack_with_priority(items, max_weight):
    # dp[weight] = 对应重量下的最大成本，初始不可达设为-1（默认成本非负）
    dp = [-1] * (max_weight + 1)
    dp[0] = 0
    # prev数组：记录每个重量状态的来源，格式是[前一个重量, 选中的物品索引]
    prev = [[-1, -1] for _ in range(max_weight + 1)]

    for item_idx, item in enumerate(items):
        idx, item_w, item_c = item['index'], item['weight'], item['cost']
        # 逆序遍历重量，避免重复选择同一物品
        for current_w in range(max_weight, item_w - 1, -1):
            prev_w = current_w - item_w
            if dp[prev_w] != -1:
                new_cost = dp[prev_w] + item_c
                # 情况1：新成本更大，直接更新状态
                if new_cost > dp[current_w]:
                    dp[current_w] = new_cost
                    prev[current_w] = [prev_w, item_idx]
                # 情况2：成本相同，暂时不处理，最后统一找最小重量
                elif new_cost == dp[current_w]:
                    pass

    # 第一步：找到最大的总成本
    max_total_cost = max(dp)
    # 第二步：在所有达到最大成本的重量中，找最小的那个
    min_total_weight = max_weight
    for w in range(max_weight + 1):
        if dp[w] == max_total_cost and w < min_total_weight:
            min_total_weight = w

    # 回溯找出选中的物品编号
    selected_items = []
    current_w = min_total_weight
    while current_w != 0:
        prev_w, item_idx = prev[current_w]
        if item_idx == -1:
            break
        selected_items.append(items[item_idx]['index'])
        current_w = prev_w
    # 反转一下，让编号顺序更合理
    selected_items.reverse()

    # 返回结果
    return {
        '最大总成本': max_total_cost,
        '对应最小总重量': min_total_weight,
        '选中物品编号': selected_items
    }

# 测试一下示例
if __name__ == '__main__':
    sample_items = [
        {'index': 1, 'weight': 2, 'cost': 3},
        {'index': 2, 'weight': 3, 'cost': 4},
        {'index': 3, 'weight': 4, 'cost': 5},
        {'index': 4, 'weight': 5, 'cost': 6}
    ]
    max_weight_limit = 8
    result = knapsack_with_priority(sample_items, max_weight_limit)
    print(f"最大总成本: {result['最大总成本']}")
    print(f"对应最小总重量: {result['对应最小总重量']}")
    print(f"选中的物品编号: {result['选中物品编号']}")

代码唠唠 #

• 逆序遍历重量：这步很关键，因为0-1背包里每个物品只能选一次，逆序遍历能保证我们处理每个物品时，之前的状态都是没选过它的，不会重复选。
• 回溯逻辑：通过prev数组，我们能从最优重量一步步倒推，找出到底选了哪些物品，最后反转一下顺序就符合直觉了。
• 优先级处理：先保证成本最大，再在这些方案里挑重量最小的，这样逻辑清晰，也不会绕晕。

小提醒 #

• 如果物品的重量或成本是0，得额外处理哦（不过一般题目里都是正整数，大概率不用操心）。
• 要是所有物品都放不进包裹，那结果就是总成本0，总重量0，选中物品为空，代码里也能正确处理这种情况。

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