【回味“经典”】DFS练习题解(工作分配问题,最大平台)

这篇文章是一年前写的 走进“深度搜索基础训练“,踏入c++算法殿堂(四)和 走进“深度搜索基础训练“,踏入c++算法殿堂(二)的重编版。

希望以此,唤起对那位故人的回忆。


【搜索与回溯算法】工作分配问题 (Standard IO)

小航看到(题面):

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目描述:

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法,为每一个人都分配一件不同的工作,并使总费用达到最小。设计一个算法,对于给定的工作费用,计算最佳工作分配方案,使总费用达到最小。

输入:

一行有1个正整数n (1≤n≤20)。接下来的n行,每行n个数,第i行表示第i个人各项工作费用。

输出:

将计算出的最小总费用输出

样例输入:

3
4 2 5
2 3 6
3 4 5

样例输出:

9

小航想到(思路)

小航看了看题,喃喃自语道:“应该可以像N皇后问题那样完成。”

(N皇后问题,详见走进“深度搜索基础训练“,踏入c++算法殿堂(二)_aliyonghang的博客-CSDN博客)

每个人都作为棋子,每份工作作为列,资金作为比较方法,一次次试,定能试出!另外,设置一个临时工费和最终公费,进行比较输出。照这样说,可以用搜索”,说着,他兴致勃勃地敲起了键盘。

小航写道(代码)

#include<iostream>
using namespace std;
const int MAX=999999999;
int q=MAX,n,c[25][25],b[25];
void dg(int x,int ps)
{
	if(x>n)
	{
		if(ps<q) q=ps;
		return;
	}
	else
	{
		for(int i=1;i<=n;i++)
		{
			if(b[i]==0)
			{
				b[i]=1;
				dg(x+1,ps+c[i][x]);
				b[i]=0;
			}
		}
	
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>c[i][j];
		}
	}
	dg(1,0);
	cout<<q;
}

但是,结果却是:

没办法,只好修改。

#include<bits/stdc++.h>
using namespace std;
int n,a[25][1000],b[1000],s,ms=100000,i,j;
void dg(int x)
{
	if(x==n)
	{
		if(s<ms)
			ms=s;
	}
	else if(s<ms)
	{
		for(int i=0;i<n;i++)
		{
			if(!b[i])
			{
				s+=a[x][i];
				b[i]=1;
				dg(x+1);
				b[i]=0;
				s-=a[x][i];
			}
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			scanf("%d",&a[i][j]);
	}
	dg(0);
	printf("%d",ms);
	return 0;
} 

再次提交,小航又得到了一个碧绿而沁人心脾的100分!

然后,他又滚动屏幕,把目光投入了下一题。


【搜索与回溯算法】最大平台 (Standard IO)

第四道题显现在屏幕中:

小航看到(题面)

时间限制: 1000 ms 空间限制: 262144 KB

题目描述:

下面是一个4×4的矩阵,它的特点是:(1)矩阵的元素都是正整数;(2)数值相等的元素相邻。这样,这个矩阵就形成了一级级“平台”,其最大的“平台”面积为8,高度(元素值)为6。若有一个 N×N的矩阵也具有上面矩阵的特点,求矩阵最大“平台”的面积和高度。
6 6 6 7
1 6 3 7
1 6 6 7
6 6 7 7

输入:

第一行为N(1≤N≤100),以下为N×N的矩阵。

输出:

第一行为平台的最大面积;
第二行为元素值。

样例输入:

4
6 6 6 7
1 6 3 7
1 6 6 7
6 6 7 7

样例输出:

8
6

小航想到(思路)

①存图:用二维数组plat存储输入

②双层for循环遍历plat,只要现点的数字未被标记(check[plat[i][j]]==0),以此为起点DFS

③每到一点,ans++,并将这一点标记为0(防止来回横跳);若相邻的点(上下左右的)符合条件(数字相同),用符合条件点继续DFS

④无路可走,结束DFS后,用ans与之前的最大平台数maxx相比较,若大于,赋值。将这一颜色标记为0.

小航写道(代码)

#include<iostream>
using namespace std;
int n,plat[105][105],check[150],ans,maxx=-1,num,lnum;
void dg(int x,int y)
{
    ++ans;
    plat[x][y]=0;
    if(plat[x+1][y]==lnum) dg(x+1,y);
    if(plat[x-1][y]==lnum) dg(x-1,y);
    if(plat[x][y+1]==lnum) dg(x,y+1);
    if(plat[x][y-1]==lnum) dg(x,y-1);
}
int main()
{
    check[0]=1;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        for(register int j=1;j<=n;++j)
        {
            cin>>plat[i][j];
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(check[plat[i][j]]==0)
            {
                lnum=plat[i][j];
                ans=0;
                dg(i,j);
                if(ans>maxx)
                {
                    maxx=ans;
                    num=lnum;
                }
                check[plat[i][j]]=1;
            }
        }
    }
    cout<<maxx<<endl<<num;
}

代码很快出来了,100分也飞快地跟了出来,第五道题一刹那间蹦了出来……

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/86471.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

python之Pandas

1.Pandas简介 Pandas 是 Python 语言的一个扩展程序库&#xff0c;用于数据分析。 Pandas 名字衍生自术语 “panel data”&#xff08;面板数据&#xff09;和 “Python data analysis”&#xff08;Python 数据分析&#xff09;。 Pandas 一个强大的分析结构化数据的工具集…

【数据结构OJ题】相交链表

原题链接&#xff1a;https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 看到这道题&#xff0c;很容易想到的方法就是暴力求解&#xff0c;就是将一个链表的每个结点的地址…

校园二手物品交易平台/二手交易系统/基于java的校园跳蚤市场系统

​ 摘 要 本文论述了校园二手物品交易平台的设计和实现&#xff0c;该网站从实际运用的角度出发&#xff0c;运用了计算机网站设计、数据库等相关知识&#xff0c;网络和Mysql数据库设计来实现的&#xff0c;网站主要包括用户注册、用户登录、浏览商品、搜索商品、查看商品并进…

【数据结构】顺序队列模拟实现

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …

React+Typescript从请求数据到列表渲染

我们在项目src目录下创建一个目录 叫 pages 在里面创建一个组件叫 list.tsx 这里 我启动了自己的java项目 创建接口 你们就也需要弄几个自己的接口做测试 然后 list.tsx 编写代码如下 import * as React from "react";export default class hello extends React.C…

uniapp 回退到指定页面 保存页面状态

uniapp 历史页面回退到指定页面。 getCurrentPages() 内容如下 let delta getCurrentPages().reverse().findIndex(item > item.route "pages/popularScience/daodi") if(delta-1){uni.navigateTo({url: /pages/popularScience/daodi,success: res > {},fa…

Blazor前后端框架Known-V1.2.13

V1.2.13 Known是基于C#和Blazor开发的前后端分离快速开发框架&#xff0c;开箱即用&#xff0c;跨平台&#xff0c;一处代码&#xff0c;多处运行。 Gitee&#xff1a; https://gitee.com/known/KnownGithub&#xff1a;https://github.com/known/Known 概述 基于C#和Blazo…

element+vue 表格行拖拽功能

解决方案 使用 sortable.js 步骤一&#xff1a; 安装 npm install vuedraggable步骤二&#xff1a;引入 import Sortable from sortablejs;步骤三&#xff1a; el-table 添加row-key属性&#xff0c;外层包一层 sortableDiv <div class"sortableDiv"> 拖…

学习开发振弦采集模块的注意事项

学习开发振弦采集模块的注意事项 &#xff08;三河凡科科技/飞讯教学&#xff09;振弦采集模块是一种用来实时采集和处理振弦信号的电子设备&#xff0c;在工业、航空、医疗等领域都有广泛应用。学习开发振弦采集模块需要注意以下几点&#xff1a; 一、硬件选择 首先需要选择…

SpeedBI数据可视化工具:浏览器上做分析

SpeedBI数据分析云是一种在浏览器上进行数据可视化分析的工具&#xff0c;它能够将数据以可视化的形式呈现出来&#xff0c;并支持多种数据源和图表类型。 所有操作&#xff0c;均在浏览器上进行 在浏览器中打开SpeedBI数据分析云官网&#xff0c;点击【免费使用】进入&#…

【C++/C 实现球球大作战】

目录 1.引言2.游戏设计&#xff1a;概述游戏的玩法和操作方式。3.游戏实现&#xff08;1&#xff09;函数 GameInit() 初始化游戏的函数。&#xff08;2&#xff09;函数 GameDraw() 用于绘制游戏场景的函数。&#xff08;3&#xff09;函数 keyControl(int speed) 负责处理键盘…

安装搭建私有仓库Harbor

目录 一、安装docker编排工具docker compose 二、安装Harbor软件包 三、修改配置文件 四、运行安装脚本 五、安装后验证 六、使用Harbor 一、安装docker编排工具docker compose 在github上选择自己想要的版本下载 https://github.com/docker/compose/releases 下载好…

Apache和Nginx各有什么优缺点,应该如何选择?

Apache和Nginx各有什么优缺点&#xff0c;应该如何选择&#xff1f; Apache和Nginx都有各自的优点和缺点&#xff0c;选择应该根据您的具体需求而定。Nginx的优点包括&#xff1a;轻量级&#xff0c;与同等web服务相比&#xff0c;Nginx占用更少的内存和资源&#xff1b;抗并发…

评测凯迪仕K70「千里眼」智能锁:不忘安全初心,便捷体验更上一层

能打败凯迪仕的&#xff0c;只有它自己。这是我们在体验过凯迪仕最新旗舰产品K70「千里眼」智能锁之后的感受。作为凯迪仕2023年最新旗舰机型&#xff0c;K70「千里眼」智能锁在配置上可以说是「机皇」般的存在。3K超高清智能锁猫眼、车规级24GHz雷达、大小双屏设计、三方可视对…

2023网络建设与运维模块三:服务搭建与运维

任务描述: 随着信息技术的快速发展,集团计划2023年把部分业务由原有的X86架构服务器上迁移到ARM架构服务器上,同时根据目前的部分业务需求进行了部分调整和优化。 一、X86架构计算机操作系统安装与管理 1.PC1系统为ubuntu-desktop-amd64系统(已安装,语言为英文),登录用户…

AlphaZero能否从围棋和国际象棋飞跃到量子计算?

一项新的研究表明&#xff0c;DeepMind惊人的游戏算法AlphaZero可以帮助释放量子计算的力量和潜力。 自两年多前出现以来&#xff0c;AlphaZero一再证明了其快速学习能力&#xff0c;将自己提升到围棋&#xff0c;国际象棋和将棋&#xff08;日本象棋&#xff09;的特级大师级别…

【MySQL】视图

目录 一、什么是视图 二、视图的操作 2.1 创建视图 2.2 删除视图 三、视图规则和限制 一、什么是视图 视图是一个虚拟表&#xff0c;其内容由查询定义。同真实的表一样&#xff0c;视图包含一系列带有名称的列和行数据。视图的数据变化会影响到基表&#xff08;创建视图所…

为什么PDF校对工具是2023年数字文档管理的必备良伴

随着企业和个人工作量的日益增长&#xff0c;PDF已成为跨平台文件交换的黄金标准。不仅仅因为它的可靠性&#xff0c;还因为它几乎可以在任何设备上查看。但与此同时&#xff0c;如何确保PDF文档的准确性和专业性呢&#xff1f;答案是使用高效的PDF校对工具。 1.全面性校对&am…

HummingBird 基于 Go 开源超轻量级 IoT 物联网平台

蜂鸟&#xff08;HummingBird&#xff09; 是 Go 语言实现的超轻量级物联网开发平台&#xff0c;包含设备接入、产品管理、物模型、告警中心、规则引擎等丰富功能模块。系统采用GoLang编写&#xff0c;占用内存极低&#xff0c; 单物理机可实现百设备的连接。 在数据存储上&…

在vue中使用codemirror格式化JSON

1. 下载指定版本的包 (避免引发不必要的错误) yarn add codemirror^5.64.02. 导入需要的文件 import CodeMirror from codemirrorimport codemirror/addon/lint/lint.cssimport codemirror/addon/fold/foldgutter.cssimport codemirror/lib/codemirror.cssimport codemirror/t…