/**

 *

 * @author Zen Johnny

 * @date 2018年3月31日 下午10:04:48

 *

 */

package freeTest.dynamicProgramming;

import java.util.Scanner;

/*动态规划之币值最大化*/

/*

	问题描述：

		给定一排n个硬币，其面值均为整数C1, C2, ..., Cn, 这些整数并不一定两两不同。

		问如何选择硬币，使得在其【原始位置互不相邻】的条件下，所选硬币的总金额最大。

*/

public class MaxAmount {

	/*动态规划算法策略*/

	/*

		递推关系：F(n)为当前的最大化币值

			F(n) = max{Cn + F(n-2),F(n-1)},n>1

			F(0)=0;F(1)=C1;

	*/

	public static double maxAmount(double coins[], int pos) {

		if(pos>1) {

			return Math.max(maxAmount(coins, pos - 2) + coins[pos], maxAmount(coins, pos - 1));

		} else if(pos == 1) {

			return coins[0];

		} else {//pos == 0

			return 0;

		}

	}

	public static void main(String args[]) {

		Scanner scanner = new Scanner(System.in);

		int size;

		double [] coins;

		System.out.println("硬币个数:");

		size = scanner.nextInt();

		coins = new double [size];

		System.out.println("请输入币值数组：");

		for(int i=0;i<size;i++) {

			coins[i] = scanner.nextDouble();

		}

		System.out.printf("[Max Amount] %f\n", maxAmount(coins, size-1));;

	}

}

硬币个数:

9

请输入币值数组：

1 1 2 10 6 2 10 8 12

[Max Amount] 33.000000