云短信平台优惠活动

 某云短信厂商，为庆祝国庆，推出充值优惠活动。
 现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。
 输入描述：
  第一行客户预算 M，其中 0 <= M <= 1000000
  第二行给出售价表，P1, P2, …, Pn, 其中 Pi 为充值 i 元获得的短信条数。
 1 <= Pi <= 1000， 1 <= n <= 100
 输出描述：最多获得的短信条数

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt();  // 读取客户预算
        sc.nextLine();  // 消耗换行符
        
        // 读取优惠售价序列，按空格分割
        String[] s = sc.nextLine().trim().split("[ ]");
        int[] getMes = new int[s.length];
        for(int i = 0; i < s.length; i++){
            // 将字符串转换为整数
            getMes[i] = Integer.parseInt(s[i]);  
        }
        
        int[] dp = new int[money + 1];
        Arrays.fill(dp,0);
        for(int i = 1;i < getMes.length + 1;i++){
            //只使用i元及一下，本身是从0开始遍历，计算每一份价格，这里从1开始是因为价格匹配
            int value = getMes[i - 1];
            for(int j = i;j <= money;j++){
                //计算当前最大金额数
                dp[j] = Math.max(dp[j],value + dp[j - i]);
            }
        }
        System.out.print(dp[money]);
    }
}

如果这题改为01背包的话

import java.util.*;

public class SMSDiscount {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt();
        sc.nextLine();
        
        String[] s = sc.nextLine().trim().split("[ ]");
        int[] getMes = new int[s.length];
        for(int i = 0; i < s.length; i++){
            getMes[i] = Integer.parseInt(s[i]);
        }
        
        int[] dp = new int[money + 1];
        Arrays.fill(dp, 0);
        int n = getMes.length;
        
        // 01背包：外层循环不变，内层循环改为倒序
        for (int i = 1; i <= n; i++) {
            int cost = i;
            int value = getMes[i - 1];
            
            // 从大到小倒序遍历，避免重复选择
            for (int j = money; j >= cost; j--) {
                dp[j] = Math.max(dp[j], dp[j - cost] + value);
            }
        }
        
        System.out.println(dp[money]);
    }
}