最后就是dp求解每一层的最大邮资问题了。拆解来看，分为向下dp和向右dp，具体dp的理解方法可以参考这篇博文，一些细节问题在下面注释中写出来了。连续邮资问题
package BackTrack; public class Postage { public static final int MAX_Postage = 300; //最大邮资不应该超过这个值 public static final int N = 6; //所用邮票张数 public static final int M = 5; //所用面值种数 public static int[] best = new int[M+1]; //存放最优解，即所有的面值best[0]不用于存储 public static int[] x = new int[M+1]; //当前解 public static int MAX = 0; //最大邮资 public static int[][] dp = new int[M+1][MAX_Postage]; //用于动态规划保存第x[0]到x[cur]的最大邮资，dp[i][j] = k表示用i种面值的邮票表示j元最少需要k张 //应该将dp数组初始化到dp[1][i] = i; 即让第一层都等于张数 public static int findMax(int cur) { if(cur == 1) { //第一层，只能用面值为1的，能表达出的最大邮资为N（张数） return N; } //向下dp int j = 1; //指示列坐标 while (dp[cur-1][j] != 0) { //此处dp的思路其实就是利用动态规划解决0-1背包问题时的思路，对新加入面值的邮票用与不用？用了用几张的问题？ //不用时 dp[cur][j] = dp[cur-1][j]; //用的时候，用几张？ for(int i = 1; i*x[cur] <= j; i++) { //i表示面值张数 int temp = dp[cur-1][j-i*x[cur]] + i; //dp[cur-1][j-i*x[cur]]表示除了新加入的面值之外前面所有的面值共同表达j-i*x[cur]元所需张数 dp[cur][j] = Math.min(temp, dp[cur][j]); //取最小的张数 } j++; } //向右dp while(true) { int temp = MAX_Postage; for(int i = 1; i <= cur; i++) { /** * 这里很妙，因为向右dp时每次都是向右一个一个推进，所以我们从x[]的第一种面值开始往上加，直到超过限制张数，那么如果x[]的 * 第二种面值刚好能将前面的多个第一种替换，那就替换更新张数 * 反正意思就是每一次for循环是对前面的较小面值的邮票是一个浓缩的过程 */ temp = Math.min(dp[cur][j-x[i]]+1, temp); } if(temp > N || temp == MAX_Postage) { //不管怎么使用当前解x[]中的已知面值，都不能在张数限制内表达出j元 break; }else { dp[cur][j] = temp; } j++; } /**对下面这条语句做一个解释 * 确保同一层上一次dp的结果不会影响下一次**尝试**时的dp，因为可能上一次尝试的一个分支中dp时已经给dp[2][10]赋过值了，但如果没有这一句 * 就会导致后面的某次尝试时一个分支中dp的时候，向下dp的时候直接将dp[2][10]向下dp了，而事实上，应该向右dp的时候才给dp[2][10]赋值的 * 其实就是向回溯的下一层发一个信号，表示这块是我上一层dp停止的地方，过了这块可能就是别的回溯分支给dp赋的值了 */ dp[cur][j] = 0; return j-1; } public static void backtrack(int t) { //t表示当前层数 if(t == M) { //已经选够最多的面值种类 int max = findMax(t); if(max > MAX) { MAX = max; for (int i = 0; i < best.length; i++) { best[i] = x[i]; } } //return; }else { int temp = findMax(t); //得到当前层的最大邮资 for(int i = x[t]+1; i <= temp+1; i++) { x[t+1] = i; backtrack(t+1); } } } public static void main(String[] args) { for (int i = 0; i <= N; i++) { dp[1][i] = i; } x[0] = 0; x[1] = 1; backtrack(1); System.out.println(MAX); for (int i = 0; i < best.length; i++) { System.out.print(best[i]+" "); } } }