云短信平台优惠活动 - 华为OD统一考试

OD统一考试

题解： Java / Python / C++

题目描述

某云短信厂商，为庆祝国庆，推出充值优惠活动。

现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。

输入描述

第一行客户预算M，其中 0<=M<=100

第二行给出售价表，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

输入
18
1 2 30 40 60 84 70 80 90 150

输出
252

题解

动态规划 完全背包问题。

对完全背包不熟，可以看 DP完全背包 进行学习。

Java

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

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        List<Integer> p = new ArrayList<>();
        while (scanner.hasNextInt()) p.add(scanner.nextInt());

        // dp[x] 表示充值 x 元最多获得的短信条数
        int[] dp = new int[M + 1];
        int len = p.size();
        for (int i = 1; i <= len; i++) { // 物品
            int cnt = p.get(i - 1); // 充值 i 元获得的短信条数
            for (int j = i; j <= M; j++) { // 容量
                dp[j] = Math.max(dp[j], dp[j - i] + cnt);
            }
        }

        System.out.println(dp[M]);
    }
}

Python

M = int(input())
p = list(map(int, input().split()))

# dp[x] 表示充值 x 元最多获得的短信条数
dp = [0] * (M + 1)
length = len(p)
for i in range(1, length + 1):  # 物品
    cnt = p[i - 1]  # 充值 i 元获得的短信条数
    for j in range(i, M + 1):  # 容量
        dp[j] = max(dp[j], dp[j - i] + cnt)

print(dp[M])

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int M;
    cin >> M;
    vector<int> p;
    int t;
    while(cin >> t) {
        p.push_back(t);
    }

    // dp[x] 表示充值 x 元最多获得的短信条数
    vector<int> dp(M + 1, 0);
    int len = p.size();
    for(int i=1; i<=len; i++) { // 物品
        int cnt = p[i-1]; // 充值i元获得的短信条数
        for(int j=i; j<=M; j++) {   // 容量
            dp[j] = max(dp[j], dp[j - i] + cnt);
        }
    }

    cout << dp[M] << endl;

    return 0;
}

相关练习题

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏