mostshadow

用户名：most2022

访问量：1800

签　名：

等　　级
排　　名	4066
经　　验	1703
参赛次数	0
文章发表	7
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

Java 重写Arrays.sort()的排序规则
浏览：146

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

蓝桥杯算法提高VIP-邮票面值设计（JAVA+思路）

　　作者: mostshadow　　　　发表时间：2022-01-22 22:15:04 浏览：382　|　评论：2　

原题链接：蓝桥杯算法提高VIP-邮票面值设计

####难点
- 与常规的深搜题目不一样，这道题没有给出明确的搜索边界
- 需要对原始问题做一个变化，将其与完全背包问题结合起来求解

####代码（含详细解析）
```
import java.util.*;

public class Test {

static int N; //允许粘贴的邮票数量
    static int K; //邮票种类数量（不同面值的邮票数量）
    static int cnt = 0; //题目中的MAX
    static int[] arr = new int[11]; //存储当前的邮票面值方案
    static int[] ans = new int[11]; //存储取得 cnt 时的邮票面值方案（即最佳方案）

public static int updateMAX(int count){
        if(count == 0){
            return 0;
        }

// 根据题目，我们要解决的原始问题是：
        // 给定N个邮票的位置，K种邮票种类，其邮票面值方案为：arr[1] ~ arr[count]，
        // 如何找到最大连续数
        // 例如N = 3, K = 2, 且 arr[1]=1,arr[2]=3(即邮票面值分别为1，3)
        // 如何组合出最大连续数
        // 1 <-- 1
        // 2 <-- 1 + 1
        // 3 <-- 1 + 1 + 1 或 3
        // 4 <-- 1 + 3
        // 5 <-- 1 + 1 + 3
        // 6 <-- 3 + 3
        // 7 <-- 1 + 3 + 3
        // 8 不满足了，因为受限于 N=3， 3+3+3-->9 而 3+3+1-->7，组合不了8的情况
        // 因此最大连续数为7

// 在这里，我们并不是直接处理上述问题，而是将其转换为
        // 完全背包问题求解（单张邮票的数量不限制）
        // 给定邮票面值方案arr[1] ~ arr[count]，且背包的最大容量为N * arr[count]
        // (因为arr[i]为单调递增数组)
        // 定义dp[i]:组合成 最大连续数i 所需的最小邮票数量
        // 状态转移方程: dp[j] = min(dp[j], dp[j-arr[i]]+1);
        // 含义：如果选择邮票arr[i]去组合 最大连续数j，则相应的背包容量要减少(即j-arr[i])，且邮票使用数量加1
        //      如果不选邮票arr[i]去组合 最大连续数j，则背包容量、邮票使用数量均不变，二者取最小
        // 那怎么去求解我们需要的最大连续数呢？
        // dp[N * arr[count]] 仅仅代表着最大连续数 N * arr[count]所需的最小邮票数量，并没有保证这个最小邮票数量 <= N
        // 因此，我们需要遍历dp数组，一遇到 dp[i] > N的时候就停止遍历，i-1即为我们所需的最大连续数

int[] dp = new int[1010];
        //dp[i]：组合出 最大连续数i 所需的最小邮票数量

//初始化dp
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

for(int i = 1; i <= count; i++){
            for (int j = arr[i]; j <= N * arr[count]; j++){
                dp[j] = Math.min(dp[j], dp[j - arr[i]]+1);
            }
        }

int i = 1;
        for(; i <= N * arr[count]; i++){
            if (dp[i] > N){
                break;
            }
        }
        return i - 1;
    }
    public static void dfs(int count, int maxSeqNum){
        if(count > K){ //说明邮票面值的取值个数为K
            if(maxSeqNum > cnt){
                //maxSeqNum:由当前邮票面值（前count个邮票）构成的最大连续数（即题目中的MAX）
                //只有maxSeqNum > cnt，需要更新答案
                cnt = maxSeqNum;
                for(int i = 1; i <= K; i++){
                    ans[i] = arr[i];
                }
            }
            return;
        }

//根据前 count-1 个邮票面值的情况，枚举第 count 个邮票面值的取值
        for(int i = arr[count-1] + 1; i <= maxSeqNum + 1; i++){
            //将当前的取值作为第count个邮票面值，然后查看是否有更优的最大连续数
            arr[count] = i;

//递归到下一层，确定第count+1个邮票面值
            //利用updateMAX()更新前count个邮票面值组合得到的最大连续数
            dfs(count+1, updateMAX(count));
        }

}
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

//邮票面值一定会包含1，且设置前0个邮票对应的最大连续数为0
        dfs(1, 0);

for(int i = 1; i <= K; i++){
            System.out.printf(ans[i] + " ");
        }
        System.out.println();
        System.out.println("MAX=" + cnt);
    }
}

```

0.0分

8 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

黄志颖

这些题我绕来绕去都快把自己绕晕了

2022-01-22 23:36:04

黄志颖

写的真的很好，我写注释的时候就老是感觉有些东西不知道怎么去形容它

2022-01-22 22:42:44

mostshadow

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

C语言程序设计教程（第三版）课后习题9.1 （C++代码）

简单的a+b （C语言代码）

蓝桥杯算法提高VIP-邮票面值设计（JAVA+思路）

评论区

精彩推荐

A+B for Input-Output Practice (II) （C语言代码）

WU-整数平均值（C++代码）

用筛法求之N内的素数。（C语言代码）

母牛的故事（C语言代码）

Minesweeper （C语言描述，蓝桥杯）

数字游戏（C++代码）

1035 题解

川哥的吩咐（C语言代码）

敲七（C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

mostshadow

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-同因查找 （C++代码）（42的倍数，，所以直接递加42输出）

C语言程序设计教程（第三版）课后习题9.1 （C++代码）

简单的a+b （C语言代码）

蓝桥杯算法提高VIP-邮票面值设计（JAVA+思路）

评论区

精彩推荐

A+B for Input-Output Practice (II) （C语言代码）

WU-整数平均值 （C++代码）

用筛法求之N内的素数。 （C语言代码）

母牛的故事 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

数字游戏 （C++代码）

1035 题解

川哥的吩咐 （C语言代码）

敲七 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

　　评论区

WU-整数平均值（C++代码）

用筛法求之N内的素数。（C语言代码）

母牛的故事（C语言代码）

数字游戏（C++代码）

川哥的吩咐（C语言代码）

敲七（C语言代码）