# 题目：2024E-云短信平台优惠活动
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：背包DP/1维dp哈希表
# 代码看不懂的地方，请直接在群上提问


from collections import defaultdict

# 客户预算
target = int(input())
# 充值获得的短信条数
nums = list(map(int, input().split()))
# 把充值0元可以获得0条短信也视为一种情况
nums = [0] + nums
# 构建1维dp哈希表，dp[i]表示充值总钱数为i元时，能获得的最大短信数
dp = defaultdict(int)
# 初始化dp哈希表，dp[0] = 0表示使用0元可以获得0条短信
dp[0] = 0

# 路径无关的完全背包
# 先遍历物品nums
# i为下标，也为充值的钱数i；num为充值钱数i能获得的短信条数
for i, num in enumerate(nums[1:], 1):
    # 再顺序遍历背包
    for pre_sum in range(target+1):
        # 考虑前一个可以获得的总金额为pre_sum
        # 加上当前充值的钱数i，可以得到当前总金额cur_sum
        cur_sum = pre_sum + i
        # 当前金额必须不超过预算
        if cur_sum <= target:
            # 更新新的哈希表中的值
            dp[cur_sum] = max(dp[cur_sum], dp[pre_sum] + num)

# 输出dp哈希表中的最大值即为答案
print(max(dp.values()))

1维dp数组

# 题目：2024E-云短信平台优惠活动
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：背包DP/1维dp数组
# 代码看不懂的地方，请直接在群上提问


# 客户预算
target = int(input())
# 充值获得的短信条数
nums = list(map(int, input().split()))
# 把充值0元可以获得0条短信也视为一种情况
nums = [0] + nums
# 构建1维dp数组，dp[i]表示充值总钱数为i元时，能获得的最大短信数
dp = [0] * (target + 1)

# 路径无关的完全背包
# 先遍历物品nums
# i为下标，也为充值的钱数i；num为充值钱数i能获得的短信条数
for i, num in enumerate(nums[1:], 1):
    # 再顺序遍历背包
    for pre_sum in range(0, target-i+1):
        # 考虑前一个可以获得的总金额为pre_sum
        # 加上当前充值的钱数i，可以得到当前总金额cur_sum
        cur_sum = pre_sum + i
        dp[cur_sum] = max(dp[cur_sum], dp[pre_sum] + num)

# 输出dp数组中的最大值即为答案
print(max(dp))

Java

1维dp哈希表

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

        // 客户预算
        int target = scanner.nextInt();
        scanner.nextLine();  // 消费掉换行符

        // 充值获得的短信条数
        String[] numsStr = scanner.nextLine().split(" ");
        int[] nums = new int[numsStr.length + 1];
        for (int i = 1; i <= numsStr.length; i++) {
            nums[i] = Integer.parseInt(numsStr[i - 1]);
        }

        // 构建1维dp哈希表，dp[i]表示充值总钱数为i元时，能获得的最大短信数
        Map<Integer, Integer> dp = new HashMap<>();
        // 初始化dp哈希表，dp[0] = 0表示使用0元可以获得0条短信
        dp.put(0, 0);

        // 路径无关的完全背包
        // 先遍历物品nums
        // i为下标，也为充值的钱数i；num为充值钱数i能获得的短信条数
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            // 再顺序遍历背包
            for (int pre_sum = 0; pre_sum <= target; pre_sum++) {
                // 考虑前一个可以获得的总金额为pre_sum
                // 加上当前充值的钱数i，可以得到当前总金额cur_sum
                int cur_sum = pre_sum + i;
                // 当前金额必须不超过预算
                if (cur_sum <= target) {
                    // 更新新的哈希表中的值
                    dp.put(cur_sum, Math.max(dp.getOrDefault(cur_sum, 0), dp.getOrDefault(pre_sum, 0)+ num));
                }
            }
        }

        // 输出dp哈希表中的最大值即为答案
        int maxSms = 0;
        for (int value : dp.values()) {
            if (value > maxSms) {
                maxSms = value;
            }
        }
        System.out.println(maxSms);
    }
}

1维dp数组

import java.util.Scanner;

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

        // 客户预算
        int target = scanner.nextInt();
        scanner.nextLine();  // 消费掉换行符

        // 充值获得的短信条数
        String[] numsStr = scanner.nextLine().split(" ");
        int[] nums = new int[numsStr.length + 1];
        for (int i = 1; i <= numsStr.length; i++) {
            nums[i] = Integer.parseInt(numsStr[i - 1]);
        }

        // 构建1维dp数组，dp[i]表示充值总钱数为i元时，能获得的最大短信数
        int[] dp = new int[target + 1];

        // 路径无关的完全背包
        // 先遍历物品nums
        // i为下标，也为充值的钱数i；num为充值钱数i能获得的短信条数
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            // 再顺序遍历背包
            for (int pre_sum = 0; pre_sum <= target - i; pre_sum++) {
                // 考虑前一个可以获得的总金额为pre_sum
                // 加上当前充值的钱数i，可以得到当前总金额cur_sum
                int cur_sum = pre_sum + i;
                dp[cur_sum] = Math.max(dp[cur_sum], dp[pre_sum] + num);
            }
        }

        // 输出dp数组中的最大值即为答案
        int maxSms = 0;
        for (int sms : dp) {
            if (sms > maxSms) {
                maxSms = sms;
            }
        }
        System.out.println(maxSms);
    }
}

C++

1维dp哈希表

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    // 客户预算
    int target;
    cin >> target;

    // 充值获得的短信条数
    vector<int> nums;
    nums.push_back(0);  // 把充值0元可以获得0条短信也视为一种情况
    int num;
    while (cin >> num) {
        nums.push_back(num);
        if (cin.peek() == '\n') break;
    }

    // 构建1维dp哈希表，dp[i]表示充值总钱数为i元时，能获得的最大短信数
    unordered_map<int, int> dp;
    // 初始化dp哈希表，dp[0] = 0表示使用0元可以获得0条短信
    dp[0] = 0;

    // 路径无关的完全背包
    // 先遍历物品nums
    // i为下标，也为充值的钱数i；num为充值钱数i能获得的短信条数
    for (int i = 1; i < nums.size(); i++) {
        int num = nums[i];
        // 再顺序遍历背包
        for (int pre_sum = 0; pre_sum <= target; pre_sum++) {
            if (dp.find(pre_sum) != dp.end()) {
                // 考虑前一个可以获得的总金额为pre_sum
                // 加上当前充值的钱数i，可以得到当前总金额cur_sum
                int cur_sum = pre_sum + i;
                // 当前金额必须不超过预算
                if (cur_sum <= target) {
                    // 更新新的哈希表中的值
                    dp[cur_sum] = max(dp[cur_sum], dp[pre_sum] + num);
                }
            }
        }
    }

    // 输出dp哈希表中的最大值即为答案
    int maxSms = 0;
    for (const auto& pair : dp) {
        if (pair.second > maxSms) {
            maxSms = pair.second;
        }
    }
    cout << maxSms << endl;

    return 0;
}

1维dp数组

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 客户预算
    int target;
    cin >> target;

    // 充值获得的短信条数
    vector<int> nums;
    nums.push_back(0);  // 把充值0元可以获得0条短信也视为一种情况
    int num;
    while (cin >> num) {
        nums.push_back(num);
        if (cin.peek() == '\n') break;
    }

    // 构建1维dp数组，dp[i]表示充值总钱数为i元时，能获得的最大短信数
    vector<int> dp(target + 1, 0);

    // 路径无关的完全背包
    // 先遍历物品nums
    // i为下标，也为充值的钱数i；num为充值钱数i能获得的短信条数
    for (int i = 1; i < nums.size(); i++) {
        int num = nums[i];
        // 再顺序遍历背包
        for (int pre_sum = 0; pre_sum <= target - i; pre_sum++) {
            // 考虑前一个可以获得的总金额为pre_sum
            // 加上当前充值的钱数i，可以得到当前总金额cur_sum
            int cur_sum = pre_sum + i;
            dp[cur_sum] = max(dp[cur_sum], dp[pre_sum] + num);
        }
    }

    // 输出dp数组中的最大值即为答案
    cout << *max_element(dp.begin(), dp.end()) << endl;

    return 0;
}

时空复杂度

时间复杂度：O(NM)。需要遍历N个不同的数字，每个数字都要考虑M种前置情况。其中M = len(dp)。

空间复杂度：O(M)。dp数组/哈希表所占空间。