最小化成本达成目标价值的背包变种问题求解方法咨询

核心思路 #

这是背包问题的典型变种，核心逻辑是把常规背包“重量限制下最大化价值”的目标反转，变为“价值达标（≥X）时最小化成本”，同时获取对应最小成本的物品数量。动态规划（DP）是解决这类问题的最优方案，下面分**0-1背包（物品不可重复选取）和完全背包（物品可重复选取）**两种场景说明。

动态规划解法步骤 #

1. 定义DP状态 #

我们需要维护两个一维DP数组：

• dp_cost[j]：总价值恰好为j时的最小成本
• dp_count[j]：总价值恰好为j时，达到最小成本所需的物品数量

初始状态设置：

• dp_cost[0] = 0（价值为0时成本为0）
• dp_count[0] = 0（价值为0时物品数量为0）
• 其他所有dp_cost[j]和dp_count[j]初始化为无穷大（表示无法达到该价值状态）

2. 状态转移（0-1背包场景） #

对于每个物品i（成本c_i，价值v_i），从后往前遍历价值j（遍历范围为X + max_v到v_i，max_v是单个物品的最大价值，确保覆盖总价值≥X的所有可能情况）：

• 如果dp_cost[j - v_i] + c_i < dp_cost[j]：
  • 更新dp_cost[j] = dp_cost[j - v_i] + c_i
  • 更新dp_count[j] = dp_count[j - v_i] + 1
• 如果dp_cost[j - v_i] + c_i == dp_cost[j]：
  • 若dp_count[j - v_i] + 1 < dp_count[j]，则更新dp_count[j]为更小的物品数量

3. 状态转移（完全背包场景） #

与0-1背包逻辑一致，仅遍历顺序改为从前往后（因为物品可重复选取）：

• 对于每个物品i，从v_i到X + max_v遍历价值j：
  • 同样按照“成本优先、数量次之”的规则更新dp_cost[j]和dp_count[j]

4. 结果计算 #

遍历所有j ≥ X的状态，找到dp_cost[j]最小的那个j，对应的dp_count[j]就是答案。如果所有j ≥ X的dp_cost[j]仍为无穷大，说明无法达成目标价值X。

优化说明 #

• 空间优化：使用一维数组即可完成计算，无需二维数组，大幅降低空间复杂度。
• 范围优化：将DP数组的上限设为X + max_v即可，无需计算到所有物品的总价值，因为超过X后，我们只需要找最小成本的情况，多余的价值计算无意义。

示例代码（0-1背包场景） #

def min_item_count(n, c, v, X):
    max_v = max(v) if v else 0
    max_j = X + max_v
    INF = float('inf')
    dp_cost = [INF] * (max_j + 1)
    dp_count = [INF] * (max_j + 1)
    dp_cost[0] = 0
    dp_count[0] = 0
    
    for i in range(n):
        ci = c[i]
        vi = v[i]
        # 0-1背包从后往前遍历，避免重复选取同一物品
        for j in range(max_j, vi - 1, -1):
            if dp_cost[j - vi] + ci < dp_cost[j]:
                dp_cost[j] = dp_cost[j - vi] + ci
                dp_count[j] = dp_count[j - vi] + 1
            elif dp_cost[j - vi] + ci == dp_cost[j]:
                if dp_count[j - vi] + 1 < dp_count[j]:
                    dp_count[j] = dp_count[j - vi] + 1
    
    # 筛选所有达标价值中的最优解
    min_cost = INF
    result = INF
    for j in range(X, max_j + 1):
        if dp_cost[j] < min_cost:
            min_cost = dp_cost[j]
            result = dp_count[j]
        elif dp_cost[j] == min_cost:
            if dp_count[j] < result:
                result = dp_count[j]
    return result if result != INF else -1  # -1表示无法达成目标

注意事项 #

• 如果要求总价值恰好等于X，只需检查j=X的状态即可，无需遍历j>X的情况。
• 若存在价值为0的物品，可直接过滤，因为这类物品只会增加成本和数量，对达成目标价值无帮助。

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