蓝桥杯算法提高VIP-邮票面值设计（java代码）

解题思路:
        深度优先遍历就可以，可以把一个设计完的邮票面值组合看作在长度减一的邮票组合的基础上再加上一个邮票面值。最后再依次对设计完的邮票面值组合进行计算其所能连续达到的最大邮资就可以。详情在代码注释。
注意事项:

参考代码:

import java.util.ArrayList;
import java.util.Scanner;


public class Main {  
	public static int max;//记录最大邮资
	public static ArrayList<Integer> result = new ArrayList<Integer>();//记录可以达成题设的最终邮票面值
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		ArrayList<Integer> value = new ArrayList<Integer>();//记录邮票设计面值
		value.add(1);//因为需要从一开始连续达到最大邮资，故肯定需要一个邮票面值为1
		DFS(value, n, k);//深度优先遍历
		for (Integer integer : result) {//输出结果
			System.out.print(integer + " ");
		}
		System.out.println();
		System.out.print("MAX=" + max);
	}
	
	public static void DFS(ArrayList<Integer> value, int n, int k) {
		if(value.size() == k) {//当设计完面值的邮票数目达到了题目要求的最大邮票数量时就开始依次求得每个邮票面值组合可以连续达到的最大邮资
			isBest(value, n, k);
			return;
		}else {
			int previous = value.get(value.size()-1);
			for (int i = previous + 1; i <= previous * n + 1; i++) {
				value.add(i);
				DFS(value, n, k);
				value.remove(value.size()-1);
			}
		}
	}
	//value为一个设计完的邮票面值集合，isBest检测他可以连续达到的最大邮资
	public static void isBest(ArrayList<Integer> value, int n, int k) {
		ArrayList<Integer> minNumber = new ArrayList<Integer>();//存储达到每一个邮资所需要的最小邮票数，下标为邮资，存储的值为邮票数
		minNumber.add(0);//达到零邮资的邮票数必然为零
		while (true) {
			int min = Integer.MAX_VALUE;//存储达到当前邮资所需要的最小邮票数
			int tempValueSum = minNumber.size();//存储当前需要达成的邮资
			for (int i = 0; i < value.size() && value.get(i) <= tempValueSum; i++) {//遍历每一个面值小于等于当前邮资的邮票，因为大于当前邮资的邮票无法组成当前邮资
				if (minNumber.get(tempValueSum - value.get(i)) + 1 < min) {//假设当前需要达到的邮资为5，加入的邮票面值为3，那么我就要比较在邮资为2时所需要的最小邮票数加上1是否小于当前邮资为5所需要的最小邮票数，如果小于就更新最小邮票数，遍历完需要遍历的邮票面值即可
					min = minNumber.get(tempValueSum - value.get(i)) + 1;
				}
			}
			if(min > n) {//如果最小需要的邮票数大于所能贴的邮票数，则无法达到当前邮资值，当前邮资即为所能连续达到的邮资
				break;
			}else {//如果小于那就说明可以达到，将最小需要的邮票数加入集合
				minNumber.add(min);
			}
		}
		if (minNumber.size()-1 > max) {//最终最小邮票数的集合大小减一就表示可以连续达到的最大邮资，因为有零的存在所以要减一，如果连续达到的邮资大于之前遍历的邮票面值组合所能连续达到的最大邮资，就更新结果
			max = minNumber.size() - 1;
			result.clear();
			result.addAll(value);
		}
	}
}