alex

用户名：dotcpp0711538

访问量：152

签　名：

等　　级
排　　名	22761
经　　验	647
参赛次数	0
文章发表	6
年　　龄	23
在职情况	学生
学　　校	福建农林大学金山学院
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

买不到的数目(鸽巢原理和动态规划)
浏览：74

你可能喜欢

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

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

买不到的数目(鸽巢原理和动态规划)

　　作者: alex　　　　发表时间：2023-11-24 16:34:39 浏览：74　|　评论：0　

原题链接：蓝桥杯2013年第四届真题-买不到的数目

## 1. 鸽巢原理
假设我们有两种包装的糖果，每包分别含有 a 和 b 颗糖果。我们想找到最大的数字 N，使得无法通过这两种包装组合得到 N 颗糖果。

建立鸽巢：我们可以将每个可能的糖果总数想象成一个“鸽巢”。

确定鸽子的数量：因为我们有两种包装，所以每种组合（即每种可能的 x 和 y 值，其中 ax + by = n）可以视为一个“鸽子”。

寻找重复组合：如果我们有超过 ab 种组合（即鸽子数量），根据鸽巢原理，至少有两个不同的 (x, y) 组合会产生相同的糖果总数。这意味着，当我们考虑的糖果总数超过 ab - 1 时，我们总能找到一种组合方式。

确定最大无法组合数：因此，最大的不可组合数就是 ab - a - b，这是因为这是小于 ab 的最大数，而任何更大的数都可以通过至少两种方式组合得到。
	
    public class Main {
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    	    int a = scanner.nextInt();
    	    int b = scanner.nextInt();
    
            // 计算并输出最大不可组合数
            int maxUnreachable = findMaxUnreachable(a, b);
            System.out.println(maxUnreachable);
        }
    
        private static int findMaxUnreachable(int a, int b) {
            // 根据鸽巢原理计算最大不可组合数
            return a * b - a - b;
        }
    }

## 2. 动态规划
建立状态数组：创建一个布尔型数组 dp，其中 dp[i] 表示使用给定的糖果包装（a 和 b 颗糖一包）能否组合出 i 颗糖果。

初始化：将 dp[0] 设置为 true，表示0颗糖果是可以实现的（不取任何糖果包装），其他所有 dp[i] 初始设为 false。

状态转移：遍历数组，对于每个 i（从 min(a, b) 到 a * b），如果 dp[i - a] 或 dp[i - b] 为 true，则设置 dp[i] 为 true。这表示如果能组合出 i - a 颗或 i - b 颗糖果，我们也能组合出 i 颗糖果。

找到最大不可组合数：从 a * b 开始向下遍历 dp 数组，找到第一个 dp[i] 为 false 的索引，这个索引就是最大的不可组合数。

```java
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
	    int a = scanner.nextInt();
	    int b = scanner.nextInt();

// 计算并输出最大不可组合数
        int maxUnreachable = maxUnreachable(a, b);
        System.out.println(maxUnreachable);
    }

private static int maxUnreachable(int a, int b) {
        boolean[] dp = new boolean[a * b];
        dp[0] = true;

for (int i = 1; i < a * b; i++) {
            if ((i >= a && dp[i - a]) || (i >= b && dp[i - b])) {
                dp[i] = true;
            }
        }

for (int i = a * b - 1; i >= 0; i--) {
            if (!dp[i]) {
                return i;
            }
        }

return -1;
    }

}

```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

alex

TA的其他文章

你可能喜欢

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

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

蛇行矩阵（C语言代码）

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

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

买不到的数目(鸽巢原理和动态规划)

评论区

精彩推荐

大神老白（C语言代码）

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

数对（C语言代码）

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

C二级辅导-等差数列（C语言代码）

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

10月月赛题解

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

1415题求解

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

alex

TA的其他文章

你可能喜欢

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

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

蛇行矩阵 （C语言代码）

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

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

买不到的数目(鸽巢原理和动态规划)

评论区

精彩推荐

大神老白 （C语言代码）

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

数对 （C语言代码）

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

C二级辅导-等差数列 （C语言代码）

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

10月月赛题解

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

1415题求解

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

蛇行矩阵（C语言代码）

　　评论区

大神老白（C语言代码）

数对（C语言代码）

C二级辅导-等差数列（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）