题目链接：https://www.dotcpp.com/oj/problem1576.html

    1. import java.util.*;
    3. public class Test {
    5.     static int N; //允许粘贴的邮票数量
    6.     static int K; //邮票种类数量（不同面值的邮票数量）
    7.     static int cnt = 0; //题目中的MAX
    8.     static int[] arr = new int[11]; //存储当前的邮票面值方案
    9.     static int[] ans = new int[11]; //存储取得 cnt 时的邮票面值方案（即最佳方案）
    11.     public static int updateMAX(int count){
    12.         if(count == 0){
    13.             return 0;
    14.         }
    16.         // 根据题目，我们要解决的原始问题是：
    17.         // 给定N个邮票的位置，K种邮票种类，其邮票面值方案为：arr[1] ~ arr[count]，
    18.         // 如何找到最大连续数
    19.         // 例如N = 3, K = 2, 且 arr[1]=1,arr[2]=3(即邮票面值分别为1，3)
    20.         // 如何组合出最大连续数
    21.         // 1 <-- 1
    22.         // 2 <-- 1 + 1
    23.         // 3 <-- 1 + 1 + 1 或 3
    24.         // 4 <-- 1 + 3
    25.         // 5 <-- 1 + 1 + 3
    26.         // 6 <-- 3 + 3
    27.         // 7 <-- 1 + 3 + 3
    28.         // 8 不满足了，因为受限于 N=3， 3+3+3-->9 而 3+3+1-->7，组合不了8的情况
    29.         // 因此最大连续数为7
    31.         // 在这里，我们并不是直接处理上述问题，而是将其转换为
    32.         // 完全背包问题求解（单张邮票的数量不限制）
    33.         // 给定邮票面值方案arr[1] ~ arr[count]，且背包的最大容量为N * arr[count]
    34.         // (因为arr[i]为单调递增数组)
    35.         // 定义dp[i]:组合成 最大连续数i 所需的最小邮票数量
    36.         // 状态转移方程: dp[j] = min(dp[j], dp[j-arr[i]]+1);
    37.         // 含义：如果选择邮票arr[i]去组合 最大连续数j，则相应的背包容量要减少(即j-arr[i])，且邮票使用数量加1
    38.         //      如果不选邮票arr[i]去组合 最大连续数j，则背包容量、邮票使用数量均不变，二者取最小
    39.         // 那怎么去求解我们需要的最大连续数呢？
    40.         // dp[N * arr[count]] 仅仅代表着最大连续数 N * arr[count]所需的最小邮票数量，并没有保证这个最小邮票数量 <= N
    41.         // 因此，我们需要遍历dp数组，一遇到 dp[i] > N的时候就停止遍历，i-1即为我们所需的最大连续数
    43.         int[] dp = new int[1010];
    44.         //dp[i]：组合出 最大连续数i 所需的最小邮票数量
    46.         //初始化dp
    47.         Arrays.fill(dp, Integer.MAX_VALUE);
    48.         dp[0] = 0;
    50.         for(int i = 1; i <= count; i++){
    51.             for (int j = arr[i]; j <= N * arr[count]; j++){
    52.                 dp[j] = Math.min(dp[j], dp[j - arr[i]]+1);
    53.             }
    54.         }
    56.         int i = 1;
    57.         for(; i <= N * arr[count]; i++){
    58.             if (dp[i] > N){
    59.                 break;
    60.             }
    61.         }
    62.         return i - 1;
    63.     }
    64.     public static void dfs(int count, int maxSeqNum){
    65.         if(count > K){ //说明邮票面值的取值个数为K
    66.             if(maxSeqNum > cnt){
    67.                 //maxSeqNum:由当前邮票面值（前count个邮票）构成的最大连续数（即题目中的MAX）
    68.                 //只有maxSeqNum > cnt，需要更新答案
    69.                 cnt = maxSeqNum;
    70.                 for(int i = 1; i <= K; i++){
    71.                     ans[i] = arr[i];
    72.                 }
    73.             }
    74.             return;
    75.         }
    77.         //根据前 count-1 个邮票面值的情况，枚举第 count 个邮票面值的取值
    78.         for(int i = arr[count-1] + 1; i <= maxSeqNum + 1; i++){
    79.             //将当前的取值作为第count个邮票面值，然后查看是否有更优的最大连续数
    80.             arr[count] = i;
    82.             //递归到下一层，确定第count+1个邮票面值
    83.             //利用updateMAX()更新前count个邮票面值组合得到的最大连续数
    84.             dfs(count+1, updateMAX(count));
    85.         }
    87.     }
    88.     public static void main(String[] args) {
    89.         Scanner sc = new Scanner(System.in);
    90.         N = sc.nextInt();
    91.         K = sc.nextInt();
    93.         dfs(1, 0);
    94.         for(int i = 1; i <= K; i++){
    95.             System.out.printf(ans[i] + " ");
    96.         }
    97.         System.out.println();
    98.         System.out.println("MAX=" + cnt);
    100.     }
    101. }