给定一个数组，包含电能（可正可负）与对应的价格，每个数组元素只能选一次，求以最小的价格，达到电能总和为1，如果不存在，则返回-1.

这是一个“带负权的 0/1 子集和最小代价”问题。每个元素只能选一次，能量可正可负，要求选出若干元素使能量和恰为 1，且价格之和最小。

两种通用做法：

  • 字典 DP（推荐，简单易写）：用字典维护“能量和 -> 最小价格”，逐个物品转移。适合 n 较大、但可达状态不爆炸的场景。
  • 分治 Meet-in-the-Middle（适合 n ≤ 40）：把数组分成两半，枚举两边所有子集，合并得到目标和。

Python 实现

  1. 字典 DP（能量/价格为整数）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    from typing import List, Tuple

    def min_price_to_energy_one(items: List[Tuple[int, int]]) -> int:
        """
        items: [(energy, price)], energy 可正可负，price >= 0（可支持负价，算法也成立）
        返回达到能量和恰为 1 的最小总价，若不可达返回 -1
        """
        INF = 10**18
        dp = {0: 0}  # 能量和 -> 最小价格
        best = INF

        for e, p in items:
            # 用上一轮的快照做 0/1 转移
            prev = dp
            cur = dict(prev)  # 不选该物品
            for s, cost in prev.items():
                ncost = cost + p
                if ncost >= best:  # 剪枝：若已有更优的答案，则不必扩展更贵状态
                    continue
                ns = s + e
                if ncost < cur.get(ns, INF):
                    cur[ns] = ncost
            dp = cur
            if 1 in dp and dp[1] < best:
                best = dp[1]

        return -1 if best == INF else best

    # 简单测试
    if __name__ == "__main__":
        items = [(2, 5), (-1, 2), (0, 3), (1, 10)]
        print(min_price_to_energy_one(items))  # 7（选 2 和 -1）

复杂度

  • 时间 O(n · M)，M 为“可达能量和”的个数（用字典仅保留可达状态，通常远小于值域）。

  • 空间 O(M)。

  • 可加更激进的剪枝：比如定期丢弃代价明显劣于当前最优的状态。

  • 若 n 很大且能量跨度极广导致状态数爆炸，问题本身就可能接近 NP 难；可结合启发式剪枝或改用近似算法。需要具体数据规模我可以进一步优化。

inf解释：

Python 中有表示正无穷 (INF) 和负无穷 (-INF) 的方法，常用于初始化最小值或最大值时。

1
2
3
4
5
6
7
INF = float('inf')
NEG_INF = float('-inf')

a = float('inf')
b = 100

print(a > b)  # 输出 True