东莞网站建设_东莞网页设计,网站色调代号,爱站挖词,微信公众号登录入口下载题目描述
某云短信厂商#xff0c;为庆祝国庆#xff0c;推出充值优惠活动。 现在给出客户预算#xff0c;和优惠售价序列#xff0c;求最多可获得的短信总条数。 输入描述#xff1a; 第一行客户预算 M M M#xff0c;其中 0 M 1000000 0M100000…题目描述
某云短信厂商为庆祝国庆推出充值优惠活动。 现在给出客户预算和优惠售价序列求最多可获得的短信总条数。 输入描述 第一行客户预算 M M M其中 0 M 1000000 0M1000000 0M1000000 第二行给出售价表 P 1 , P 2... P n P1,P2...Pn P1,P2...Pn, 其中 1 n 100 1n100 1n100 P i Pi Pi 为充值i元获得的短信条数。 1 P i 1000 1 n 100 1Pi1000 1n100 1Pi10001n100
输出描述
最多获得的短信条数 补充说明
示例1 输入 6 10 20 30 40 60 输出 70 说明 分两次充值最优1元、5元各充一次。总条数 106070
示例2
输入 15 10 20 30 40 60 60 70 80 90 150 输出 210 说明 分两次充值最优10元、5元各充一次。总条数 15060210
题解
这个是一个完全背包问题 动态规划来解决
但是这里的 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.length1];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]);}
}
