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));
    for (int i = 0; i < n; i++) {
        scanf("%d", &powers[i]);
    }

    scanf("%d", &p_max);

    int result = solve(n, powers, p_max);
    printf("%d\n", result);

    free(powers);  // 释放动态分配的内存
    return 0;
}

• Javascript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];

rl.on('line', (line) => {
    inputLines.push(line);
});

rl.on('close', () => {
    const n = parseInt(inputLines[0]);
    const powers = inputLines[1].split(' ').map(Number);
    const p_max = parseInt(inputLines[2]);
    
    console.log(solve(n, powers, p_max));
});

function solve(n, powers, p_max) {
    // 初始化dp数组，dp[i]表示是否可以达到功率i
    let dp = new Array(p_max + 1).fill(false);
    dp[0] = true;  // 总是可以达到0功率

    // 遍历每个充电设备的功率
    for (let power of powers) {
        for (let i = p_max; i >= power; i--) {
            if (dp[i - power]) {
                dp[i] = true;
            }
        }
    }

    // 从p_max开始向下查找第一个为true的索引
    for (let i = p_max; i >= 0; i--) {
        if (dp[i]) {
            return i;
        }
    }

    return 0;  // 如果没有找到合适的组合，返回0
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int[] powers = new int[n];
        for (int i = 0; i < n; i++) {
            powers[i] = scanner.nextInt();
        }
        int p_max = scanner.nextInt();
        
        System.out.println(solve(n, powers, p_max));
        
        scanner.close();
    }
    
    public static int solve(int n, int[] powers, int p_max) {
        // 初始化dp数组，dp[i]表示是否可以达到功率i
        boolean[] dp = new boolean[p_max + 1];
        dp[0] = true;  // 总是可以达到0功率
        
        // 遍历每个充电设备的功率
        for (int power : powers) {
            for (int i = p_max; i >= power; i--) {
                if (dp[i - power]) {
                    dp[i] = true;
                }
            }
        }
        
        // 从p_max开始向下查找第一个为true的索引
        for (int i = p_max; i >= 0; i--) {
            if (dp[i]) {
                return i;
            }
        }
        
        return 0;  // 如果没有找到合适的组合，返回0
    }
}

• Cpp

#include <iostream>
#include <vector>

using namespace std;

int solve(int n, vector<int>& powers, int p_max) {
    // 初始化dp数组，dp[i]表示是否可以达到功率i
    vector<bool> dp(p_max + 1, false);
    dp[0] = true;  // 总是可以达到0功率

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

    // 从p_max开始向下查找第一个为true的索引
    for (int i = p_max; i >= 0; i--) {
        if (dp[i]) {
            return i;
        }
    }

    return 0;  // 如果没有找到合适的组合，返回0
}

int main() {
    int n, p_max;
    cin >> n;

    vector<int> powers(n);
    for (int i = 0; i < n; i++) {
        cin >> powers[i];
    }

    cin >> p_max;

    cout << solve(n, powers, p_max) << endl;

    return 0;
}