1092: 最大价值(dollars) 算法 动态规划
题目地址：http://www.hustoj.com/oj/problem.php?id=1092
题目描述
Dave以某种方法获取了未来几天美元对德国马克的兑换率。现在Dave只有100美元，请编程序，使Dave通过几天的美元与德国马克的兑换后能得到最多的美元。
输入
第1行包含一个自然数n(l≤n≤I00)，表示Dave所知道的兑换率的天数。
后面跟着n个自然数A (100≤A≤I000)。第i+l行的数A表示第i天的兑换率。它告诉那天他能用100美元购买A马克，或用A马克购买100美元。
输出
只有1行，输出Dave经过n天的兑换后能得到的最多的美元值。结果保留两位小数。注意不一定每天都需要兑换。
说明：由于实数运算存在误差，结果在0.05的误差范围内将被认为是正确的。
样例输入
3 100 150 200 5 400 300 500 300 250
样例输出
200.00 //用力错误，正常输出应该是100 266.66
提示
样例2说明：
第一天：100美元换成400德国马克
第二天：400德国马克换成133.3333美元
第三天：133.3333美元换成666.6666德国马克
第四天：不换
第五天：666.6666德国马克换成266.6666美元
解题思路：
使用动态规划记录每一天的历史的最大价值，然后最后根据历史价值求解！
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | package com.daxin; import java.util.Arrays; import java.util.Scanner; /** * Created by Daxin on 2017/8/20. * 动态规划 */ public class MaxDollarValue { public static void main(String[] args) { // Scanner cin = new Scanner(System.in); // int n = cin.nextInt(); // // int[] nums = new int[n]; // // for (int i = 0; i < n; i++) { // nums[i] = cin.nextInt(); // } int [] nums = { 400 , 300 , 500 , 300 , 250 }; // int[] nums2 = {100, 150, 200}; // System.out.println(getMaxValue(nums1)); System.out.println(getMaxValue(nums)); } public static double getMaxValue( int [] nums) { int len = nums.length; double [][] table = new double [len][len + 1 ]; // table[ 0 ][ 1 ] = 1 ; for ( int i = 0 ; i < table.length; i++) { table[i][ 0 ] = nums[i]; } for ( int i = 2 ; i < table[ 0 ].length; i++) { for ( int j = 1 ; j < table.length; j++) { double noChange = table[j - 1 ][i - 1 ]; double change = noChange * nums[j - 1 ] * 1.0 / nums[j]; table[j][i] = noChange > change ? noChange : change; } } for ( double []ds :table){ System.out.println(Arrays.toString(ds)); } return Math.floor(table[table.length - 1 ][table[ 0 ].length - 1 ] * 10000 ) / 100 ; } } |
转载于:https://www.cnblogs.com/wangsicongde/p/7576887.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！