查找充电设备组合

题目描述

某个充电站, 可提供 n 个充电设备, 每个充电设备均有对应的输出功率.

任意个充电设备组合的输出功率总和, 均构成功率集合 P 的 1 个元素.

功率集合 P 的最优元素, 表示最接近充电站最大输出功率 p_max 的元素.

输入描述

输入为 3 行:

• 第 1 行为充电设备个数 n
• 第 2 行为每个充电设备的输出功率
• 第 3 行为充电站最大输出功率 p_max

备注:

• 充电设备个数 n > 0
• 最优元素必须小于或等于充电站最大输出功率 p_max

输出描述

功率集合 P 的最优元素.

示例1

输入:

4
50 20 20 60
90

输出:

90

示例2

输入:

2
50 40
30

输出:

0

示例3

输入:

3
1 2 3
5

输出:

5

题解

Python

def main():
    # 读取输入
    # 机器数量
    num_machines = int(input())
    assert 0 < num_machines
    # 每台机器的输出功率
    machine_powers = list(map(int, input().split()))
    assert len(machine_powers) == num_machines
    # 最大输出功率
    max_power = int(input())

    # 背包问题, DP
    # 思路一: 暴力法, 时间复杂度 O(2^n)

    target_power = 0

    def recursive(machine_index, power_sum):
        # 所有机器都访问完了
        if machine_index >= num_machines:
            diff = max_power - power_sum
            nonlocal target_power
            if 0 <= diff < (max_power - target_power):
                target_power = power_sum
            return

        # 递归调用
        recursive(machine_index + 1, power_sum + machine_powers[machine_index])
        recursive(machine_index + 1, power_sum)

    recursive(0, 0)

    # 打印结果
    print(target_power)

if __name__ == "__main__":
    main()