2023年华为OD机考真题：查找充电设备组合

算法刷题1年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：查找充电设备组合
时间限制：5s 空间限制：256MB 限定语言：不限
题目描述：
某个充电站，可提供n个充电设备，每个充电设备均有对应的输出功率。任意个充电设备组合的输出功率总和，均构成功率集合P的1个元素。功率集合P的最优元素，表示最接近充电站最大输出功率p_max的元素。
输入描述：
输入为3行：
第1行为充电设备个数n。
第2行为每个充电设备的输出功率。
第3行为充电站最大输出功率p_max。
输出描述：
功率集合P的最优元素
补充说明：
1.充电设备个数n>0
2.最优元素必须小于或等于充电站最大输出功率p_max。
示例1
输入：
4
50 20 20 60
90
输出：
90
说明：
当充电设备输出功率50、20、20组合时，其输出功率总和为90，最接近充电站最大充电输出功率，因此最优元素为90。
示例2
输入：
2
50 40
30
输出：
0
说明：
所有充电设备的输出功率组合，均大于充电站最大充电输出功率30，此时最优元素值为0。
解题思路：
算法一：
使用回溯法对所有充电设备进行求和。
算法二：
通过双层for循环求出所有符合要求的组合的输出总功率。

代码实现一：

package com.codernav.demo.hwod.exam;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @title 查找充电设备组合
 * @Description 某个充电站，可提供n个充电设备，每个充电设备均有对应的输出功率。
 * 任意个充电设备组合的输出功率总和，均构成功率集合P的1个元素。
 * 功率集合P的最优元素，表示最接近充电站最大输出功率p_max的元素。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/14
 */
public class Main {
    public static int p_max;
    public static int max;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String[] strs = sc.nextLine().split(" ");
        p_max = sc.nextInt();
        int[] ints = Arrays.stream(strs).mapToInt(Integer::parseInt).toArray(); //字符串数组转化为正数数组
        int count = Arrays.stream(ints).sum();  //求出数组的总和
        if (count <= p_max) {
            System.out.println(count);  //总和小于等于p_max则直接输出总和
        } else {
            handle(ints, 0, 0);
            System.out.println(max);
        }
    }

    /**
     * 经典的m个数中求n个数的算法（强烈建议大家记住这个算法，很多地方可以套用）
     *
     * @param ints  正数数组
     * @param sum   功率和
     * @param index 索引
     */
    public static void handle(int[] ints, int sum, int index) {
        if (sum >= p_max || index == ints.length) {    //边界也需要输出
            if (sum == p_max) {
                max = sum;
            } else if (sum < p_max) {
                max = Math.max(max, sum);
            } else {
                max = Math.max(max, sum - ints[index - 1]);
            }
        } else {
            for (int i = index; i < ints.length; i++) {
                sum += ints[i];
                handle(ints, sum, i + 1);
                sum -= ints[i];
            }
        }
    }
}

代码实现二：

package com.codernav.demo.hwod.exam;

import java.util.*;

/**
 * @title 查找充电设备组合
 * @Description 某个充电站，可提供n个充电设备，每个充电设备均有对应的输出功率。
 * 任意个充电设备组合的输出功率总和，均构成功率集合P的1个元素。
 * 功率集合P的最优元素，表示最接近充电站最大输出功率p_max的元素。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/14
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            numbers.add(sc.nextInt());
        }
        int p_max = sc.nextInt();
        int max = 0;
        Set<Integer> objects = new HashSet<>();     //符合要求的所有组合的输出总功率
        objects.add(0);
        for (Integer number : numbers) {
            Set<Integer> objects1 = new HashSet<>();
            for (Integer object : objects) {
                int newobj = object + number;
                if (newobj <= p_max) {
                    objects1.add(newobj);
                    max = Math.max(max, newobj);
                }
            }
            objects.addAll(objects1);
        }
        System.out.println(max);
    }
}

代码实现三：背包算法题解

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 查找充电设备组合
 * @Description 某个充电站，可提供n个充电设备，每个充电设备均有对应的输出功率。
 * 任意个充电设备组合的输出功率总和，均构成功率集合P的1个元素。
 * 功率集合P的最优元素，表示最接近充电站最大输出功率p_max的元素。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/14
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = in.nextInt();
        }
        int max = in.nextInt();
        System.out.println(result(n, p, max));
    }

    public static int result(int n, int[] p, int max) {
        int[][] dp = new int[n + 1][max + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= max; j++) {
                if (i == 0 || j == 0) {
                    continue;
                }
                if (p[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], p[i - 1] + dp[i - 1][j - p[i - 1]]);
                }
            }
        }
        return dp[n][max];
    }
}