云短信平台优惠活动

题目描述

某云短信厂商，为庆祝国庆，推出充值优惠活动。
现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。
输入描述：
第一行客户预算 $M$，其中 $0<=M<=1000000$
第二行给出售价表，$P1,P\mathrm{2...}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 取值范围过大，会出现内促过大问题，需要把横向遍历修改为纵向遍历，
思路有了，代码还不知道咋写，先写一个简单的

源码Java

public class PhoneCharge {static Input input;static {input = new Input("15\n" +"10 20 30 40 60 60 70 80 90 150");}public static void main(String[] args) {int money = Integer.parseInt(input.nextLine());String[] messages = input.nextLine().split(" ");int msg[] = new int[messages.length+1];for (int i = 1; i <= messages.length; i++) {msg[i] = Integer.parseInt(messages[i-1]);}int[] dp = new int[money + 1];for (int i = 1; i < msg.length; i++) {for (int j = i; j <= money; j++) {dp[j] = Math.max(dp[j], dp[j - i] + msg[i]);}}System.out.println(dp[money]);}
}