蓝桥杯历年真题值DFS

2020年分配口罩 

【问题描述】

某市市长获得了若干批口罩，每一批口罩的数目如下：（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 mask.txt，内容与下面的文本相同）

9090400

8499400

5926800

8547000

4958200

4422600

5751200

4175600

6309600

5865200

6604400

4635000

10663400

8087200

4554000

现在市长要把口罩分配给市内的 2 所医院。由于物流限制，每一批口罩只能全部分配给其中一家医院。市长希望 2 所医院获得的口罩总数之差越小越好。请你计算这个差最小是多少？

【答案提交】

这是一道结果填空题。

我最开始以为需要把这些口罩都分给两所医院，但不是，求分的口罩数的差值最小就可以。

代码：

import java.util.Scanner;
public class Main {

//分配口罩
static int[] arr = new int[15];
static int sum = 0;
static int cha = 0x3f3f3f3f;
public static void main(String[] args) {
Scanner sc  =  new Scanner(System.in);
//将口罩数目从键盘录入
for(int i = 0; i < 15; i++) {
arr[i] = sc.nextInt();
}
//将口罩的总数目算出来
for(int i = 0; i < 15; i++) {
sum += arr[i];
}

dfs(0,0);//深度优先遍历，每一层和口罩的值
System.out.println(cha);
}
//dfs
public static void dfs(int d, int v) {
//先写递归的终止条件
if(d == 15) cha = Math.min(cha, Math.abs(sum - v - v));
else {
dfs(d + 1, v + arr[d]);
dfs(d + 1, v);
}
}
}

注意的几点：

1.若是找到比cah小的则更新cha ,所以cha不能太小，我们定义为0x3f3f3f3f,表示整形范围内一个无穷大的数。

2.递归退出时，我们算cha值，在cha和sum-两批口罩取一个较小的值

3.递归遍历的时候，层数更深，是层数！！！ 

 

 

原文地址：https://blog.csdn.net/2301_76876837/article/details/137647945

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！