E卷-查找充电设备组合(100分)

查找充电设备组合

问题描述

某个充电站可提供 个充电设备，每个充电设备均有对应的输出功率。任意个充电设备组合的输出功率总和，均构成功率集合 的 1 个元素。功率集合 的最优元素，表示最接近充电站最大输出功率 的元素。

输入格式

输入为 3 行：

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

输出格式

输出功率集合 的最优元素。

样例输入 1

4
50 20 20 60
90

样例输出 1

90

样例解释 1

当充电设备输出功率 50、20、20 组合时，其输出功率总和为 90，最接近充电站最大充电输出功率，因此最优元素为 90。

样例输入 2

2
50 40
30

样例输出 2

0

样例解释 2

所有充电设备的输出功率组合，均大于充电站最大充电输出功率 30，此时最优元素值为 0。

数据范围

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

题解

这道题目本质上是一个变形的 0-1 背包问题。

我们需要从给定的充电设备中选择一些，使得它们的总功率最接近但不超过充电站的最大输出功率。

解题思路如下：

1. 首先，我们可以使用动态规划来解决这个问题。创建一个数组 dp，其中 表示是否可以达到功率 i。

2. 初始化 = true，因为总是可以达到 功率（不选择任何设备）。

3. 遍历每个充电设备的功率，对于每个功率 power，更新 dp 数组：

   • 如果 为 true，那么 也应该为 true。

4. 最后，从 开始向下遍历 dp 数组，找到第一个为 true 的索引，即为最优解。

时间复杂度分析：

• 设充电站最大输出功率为 M，充电设备数量为 N。
• 我们需要遍历每个充电设备（N次），对于每个设备，我们需要更新 dp 数组（最多 M 次）。
• 因此，总的时间复杂度为 O(N * M)。

参考代码

• Python

def solve(n, powers, p_max):
    # 初始化dp数组，dp[i]表示是否可以达到功率i
    dp = [False] * (p_max + 1)
    dp[0] = True  # 总是可以达到0功率
    
    # 遍历每个充电设备的功率
    for power in powers:
        # 从大到小遍历，避免重复计算
        for i in range(p_max, power - 1, -1):
            if dp[i - power]:
                dp[i] = True
    
    # 从p_max开始向下查找第一个为True的索引
    for i in range(p_max, -1, -1):
        if dp[i]:
            return i
    
    return 0  # 如果没有找到合适的组合，返回0

# 读取输入
n = int(input())
powers = list(map(int, input().split()))
p_max = int(input())

# 计算并输出结果
result = solve(n, powers, p_max)
print(result)

• C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int solve(int n, int* powers, int p_max) {
    // 动态分配内存给dp数组
    bool* dp = (bool*)calloc(p_max + 1, sizeof(bool));
    dp[0] = true;  // 总是可以达到0功率

    // 遍历每个充电设备的功率
    for (int j = 0; j < n; j++) {
        for (int i = p_max; i >= powers[j]; i--) {
            if (dp[i - powers[j]]) {
                dp[i] = true;
            }
        }
    }

    // 从p_max开始向下查找第一个为true的索引
    for (int i = p_max; i >= 0; i--) {
        if (dp[i]) {
            free(dp);  // 释放动态分配的内存
            return i;
        }
    }

    free(dp);  // 释放动态分配的内存
    return 0;  // 如果没有找到合适的组合，返回0
}

int main() {
    int n, p_max;
    scanf("%d", &n);

    int* powers = (int*)malloc(n * sizeof(int));