2023年华为OD机考真题：云短信平台优惠活动

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

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

题目：云短信平台优惠活动
知识点哈希表队列数组统计贪心
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
某云短信厂商，为庆祝国庆，推出充值优惠活动。
现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。
输入描述：
第一行客户预算M，其中 0<=M<=1000000
第二行给出售价表，P1,P2…Pn, 其中 1<=n<=100，Pi为充值i元获得的短信条数。 1<=Pi<=1000， 1<=n<=100
输出描述：
最多获得的短信条数
示例1
输入：
6
10 20 30 40 60
输出：
70
说明：
分两次充值最优，1元、5元各充一次。总条数 10+60=70
示例2
输入：
15
10 20 30 40 60 60 70 80 90 150
输出：
210
说明：
分两次充值最优，10元、5元各充一次。总条数 150+60=210
解题思路：
通过回溯将所有充值的情形模拟一遍，求出其中最大的短信条数
博主使用的是M中取N个数的算法（可以套用到很多题目上），大家也可以使用其他的方法。

代码实现一：

package com.codernav.demo.hwod.exam;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @title 云短信平台优惠活动
 * @Description 某云短信厂商，为庆祝国庆，推出充值优惠活动。
 * 现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static int max = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        sc.nextLine();
        String[] P = sc.nextLine().split(" ");
        combine(P, M, new ArrayList<>(), 0);
        System.out.println(max);
    }

    /**
     * M中取N个数的算法
     *
     * @param strings 出售价表
     * @param n       剩余的预算
     * @param list    充值获得的短信条数的集合
     * @param index   出售价表的索引
     */
    public static void combine(String[] strings, int n, List<Integer> list, int index) {
        if (n == 0) {     //当预算等于0，退出循环
            int count = 0;
            for (Integer integer : list) {
                count += integer;
            }
            max = Math.max(max, count);
        } else {
            for (int i = index; i < strings.length; i++) {
                int x = Integer.parseInt(strings[i]);
                list.add(x);
                combine(strings, n - (i + 1), list, i + 1);
                list.remove(list.size() - 1);
            }
        }
    }
}

代码实现二：Java代码满分实现

package com.codernav.demo.hwod.exam;

import java.util.*;

/**
 * @title 云短信平台优惠活动
 * @Description 某云短信厂商，为庆祝国庆，推出充值优惠活动。
 * 现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        in.nextLine();
        String[] P = in.nextLine().split(" ");
        int[] nums = Arrays.stream(P).mapToInt(Integer::parseInt).toArray();
        System.out.println(buy( nums, m, new HashMap<>()));
    }

    private static int buy(int[] arr, int m, Map<Integer, Integer> cache) {
        if (cache.containsKey(m)) {
            return cache.get(m);
        }
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i+1 > m) {
                break;
            }
            ans = Math.max(ans, arr[i] + buy(arr, m - i - 1, cache));
        }
        cache.put(m, ans);
        return ans;
    }
}