题面描述

某云短信厂商为庆祝国庆，推出充值优惠活动。给定客户的预算和不同充值金额对应的短信条数，求在这个预算下最多可以获得的短信总条数

思路

这个问题可以视为一个经典的背包问题。我们需要在有限的预算下选择最优的充值方式以最大化短信条数。具体思路如下：

1. 动态规划定义：

   • 定义一个一维数组 dp，其中 dp[j] 表示在预算为 j 时能够获得的最多短信条数。
   • 初始时，dp[0] = 0（预算为0时，短信条数为0），其他所有 dp[j] 初始化为0。

2. 动态规划转移方程：

   • 对于每个售价 P[i]（即充值金额），更新所有预算 j 从大到小的值：
     • 如果当前预算 j 大于等于 P[i]，则更新 dp[j]： [ dp[j] = \max(dp[j], dp[j - (i + 1)] + P[i]) ]
   • 这里的 dp[j - (i + 1)] + P[i] 表示在预算 j - (i + 1) 时的短信条数，加上当前充值所能获得的短信条数。

3. 结果：

   • 最后，dp[M] 中的值即为在预算 M 下能够获得的最多短信条数。

cpp

#include <iostream>
#include <vector>
#include <algorithm>
# define int long long
using namespace std;

signed main() {
    int m;  // 客户预算
    cin >> m;  // 输入预算
    vector<int> p;  // 存储短信条数对应的售价
    int price;

    // 读取短信条数对应的售价
    while (cin >> price) {
        p.push_back(price);
        if (cin.peek() == '\n') break;  // 读取到换行符则停止
    }

    vector<int> dp(m + 1, 0);  // 动态规划数组，初始化为0，大小为 m+1

    // 遍历售价列表
    for (int i = 0; i < p.size(); i++) {
        // p[i]条短信花费i+1元
        // 从后向前更新动态规划数组
        for (int j = i + 1; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - (i + 1)] + p[i]);
        }
    }

    cout << dp[m] << endl;  // 输出在预算m下可以获得的最大短信条数

    return 0;
}

python

def main():
    m = int(input())  # 输入预算
    p = list(map(int, input().split()))  # 读取一行的多个售价并转为整数列表

    dp = [0] * (m + 1)  # 动态规划数组，初始化为0，大小为 m+1

    # 遍历售价列表
    for i in range(len(p)):
        # p[i]条短信花费i+1元
        # 从后向前更新动态规划数组
        for j in range(i + 1, m + 1):
            dp[j] = max(dp[j], dp[j - (i + 1)] + p[i])

    print(dp[m])  # 输出在预算m下可以获得的最大短信条数

if __name__ == "__main__":
    main()

java

import java.util.Scanner;

public class SMSRecharge {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入客户预算
        long m = scanner.nextLong();  
        scanner.nextLine();  // 读取剩余的换行符

        // 读取短信条数对应的售价
        String[] prices = scanner.nextLine().split(" ");
        long[] p = new long[prices.length];

        // 将输入的字符串转换为整数
        for (int i = 0; i < prices.length; i++) {
            p[i] = Long.parseLong(prices[i]);
        }

        // 动态规划数组，初始化为0，大小为 m+1
        long[] dp = new long[(int) (m + 1)];

        // 遍历售价列表
        for (int i = 0; i < p.length; i++) {
            // p[i]条短信花费i+1元
            // 从后向前更新动态规划数组
            for (int j = i + 1; j <= m; j++) {
                dp[j] = Math.max(dp[j], dp[j - (i + 1)] + p[i]);
            }
        }

        // 输出在预算m下可以获得的最大短信条数
        System.out.println(dp[(int) m]);  

        scanner.close();  // 关闭扫描器
    }
}

题目内容

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

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

输入描述

第一行客户预算 $M$ ，其中 $0 ≤ M ≤ 10^6$

第二行给出售价表， $P_1, P_2, … P_n$, 其中 $1 ≤ n ≤ 100$ ,

$P_i$为充值 $i$ 元获得的短信条数。$1 ≤ P_i ≤ 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