NEFU-2023-算法设计与分析实验二动态规划算法设计

news/2024/4/20 3:15:45/文章来源:https://blog.csdn.net/qq_62377885/article/details/130328823

作者的话

大底包含了算法硬性规定的作业代码，并非最优解，仅供参考并会持续更新。勿要无脑copy，对自己负责。如果代码有误或者优化建议，直接相应博客下方评论或者qq找我如果对代码有理解不了的或者疑惑可以询问我，但是请确保你已经自己思考过或者查过搜索引擎（如果我原模原样搜到了资料的话我会锤你的hh）。一些语法和库的资料查询网站受个人风格影响，部分题目解题方式可能没按照教学要求，如有必要请自己按教学要求做一遍。如果可以的话，麻烦借鉴完以后给我博客来个三连啥的，这可能对我以后找工作或者其他博客的推广什么的有些帮助，感谢

如要系统学习可看我的另一篇博客算法小课堂（四）动态规划

题目一 数字三角问题

问题描述：给定一个由n行数字组成的数字三角形，如下图所示

          7

       3   8

     8   1   0

  2    7   4   4

4    5   2   6   5

试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

如上图最大值为30=7+3+8+7+5

正序解法C++

#include <iostream>using namespace std;const int N = 510, INF = 1e9;
int f[N][N]; // f[i][j]表示到第i行第j列的最大路径和
int a[N][N]; // 存放输入的矩阵int main()
{int n;scanf("%d", &n);for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)scanf("%d", &a[i][j]);// 初始化for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)f[i][j] = -INF;f[1][1] = a[1][1];// 动态转移for (int i = 2; i <= n; i++)for (int j = 1; j <= i; j++)f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);// 求解答案int max0 = -INF;for (int j = 1; j <= n; j++)max0 = max(max0, f[n][j]);cout << max0 << endl;return 0;
}

正序解法JAVA

import java.util.*;public class Main {static final int N = 510, INF = 1_000_000_000;static int[][] f = new int[N][N]; // f[i][j]表示到第i行第j列的最大路径和static int[][] a = new int[N][N]; // 存放输入的矩阵public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)a[i][j] = sc.nextInt();// 初始化for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)f[i][j] = -INF;f[1][1] = a[1][1];// 动态转移for (int i = 2; i <= n; i++)for (int j = 1; j <= i; j++)f[i][j] = Math.max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);// 求解答案int max0 = -INF;for (int j = 1; j <= n; j++)max0 = Math.max(max0, f[n][j]);System.out.println(max0);}
}

倒序解法

f(i,j)含义: 从最底层出发到第 i 行第 j 个数的最大路径和

每个点有两种选择: 向左上方走 和 向右上方走

对应的子问题为: ​​ f(i+1,j) ​​ 和 f(i+1,j+1)

倒序情况下不需要考虑边界条件

结果: f(1,1)

#include <iostream>using namespace std;const int N = 510;
int f[N][N];int main()
{int n;cin >> n;// 读入三角形中的数值for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++)cin >> f[i][j];// 倒序 DP，从最后一行开始向上推for(int i = n; i >= 1; i--)for(int j = 1; j <= i; j++)f[i][j] += max(f[i+1][j], f[i+1][j+1]);cout << f[1][1] << endl;    // 输出最终的结果return 0;
}

二维优化为一维

#include <iostream>
using namespace std;
const int N = 510, INF = 1e9;int f[N]; // f[j]表示到达当前行第j列的最大路径和
int a[N][N]; // 存放输入的矩阵int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)scanf("%d", &a[i][j]);// 初始化for (int j = 1; j <= n; j++)f[j] = -INF;f[1] = a[1][1];// 动态转移for (int i = 2; i <= n; i++)for (int j = i; j >= 1; j--)f[j] = max(f[j], f[j - 1]) + a[i][j];// 求解答案int max0 = -INF;for (int j = 1; j <= n; j++)max0 = max(max0, f[j]);cout << max0 << endl;return 0;
}

记忆化搜索

#include <iostream>
using namespace std;const int N = 510;int n;
int d[N][N];
int f[N][N];int dfs(int i, int j) {if (i == n) return d[i][j]; // 最底层if (f[i][j] != -1) return f[i][j]; // 记忆化int l = dfs(i + 1, j);int r = dfs(i + 1, j + 1);return f[i][j] = max(l, r) + d[i][j];
}int main() {cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {cin >> d[i][j];f[i][j] = -1; // 初始化}}cout << dfs(1, 1) << endl;return 0;
}

回溯法

#include <iostream>
#include <cstring>
using namespace std;const int N = 510, INF = 1e9;
int f[N][N]; // f[i][j]表示到第i行第j列的最大路径和
int a[N][N]; // 存放输入的矩阵
int path[N];//用来记录路径void dfs(int x, int y,int n) {path[n] = a[x][y];if (x == 1) {return;}if (f[x - 1][y] > f[x - 1][y - 1]) {dfs(x - 1, y,n-1);}else {dfs(x - 1, y - 1,n-1);}
}int main()
{int n;scanf("%d", &n);for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)scanf("%d", &a[i][j]);// 初始化1/*for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)f[i][j] = -INF;*/// 初始化2memset(f,-INF,sizeof(f));f[1][1] = a[1][1];// 动态转移for (int i = 2; i <= n; i++){for (int j = 1; j <= i; j++)f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);}// 求解答案int max0 = -INF;int x = n,y=1;for (int j = 1; j <= n; j++)if (f[n][j] > f[n][y])y = j;cout << f[n][y] << endl;dfs(x,y,n);for(int i = 1;i <= n;i++)cout<<path[i]<<" ";return 0;
}

题目二最长公共子序列问题

2、最长公共子序列问题

问题描述：给定两个序列X={x1,x2,...,xm}和Y={y1,y2,...,yn},找出X和Y的最长公共子序列。

输入：

第1行：两个子序列的长度，m n

第2行：第1个子序列的各个元素（序列下标从1开始）

第3行：第2个子序列的各个元素（序列下标从1开始）

输出：

最长公共子序列

实例：

输入：

第1行：

4 5            //m和n的值

第2行

abad        //输入4个字符，下标从1开始

第3行

baade      //输入5个字符，下标从1开始

输出：

aad

实验书模板

朴素解法

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N]; // f[i][j] 表示 a 的前 i 个字符和 b 的前 j 个字符的最长公共子序列长度
int main() {cin >> n >> m >> a + 1 >> b + 1; // 输入 n、m 和字符串 a、b，注意要从下标 1 开始读入for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (a[i] == b[j]) { // 如果当前字符相同，则最长公共子序列长度加一f[i][j] = f[i - 1][j - 1] + 1;} else { // 如果当前字符不同，则最长公共子序列长度为 a 的前 i-1 个字符和 b 的前 j 个字符的最长公共子序列长度，或者是 a 的前 i 个字符和 b 的前 j-1 个字符的最长公共子序列长度中的较大值f[i][j] = max(f[i - 1][j], f[i][j - 1]);}}}// 回溯输出最长公共子序列int len = f[n][m];char ans[len+1]; // 存储最长公共子序列ans[len] = '\0'; // 字符串末尾要加上'\0'int i = n, j = m;while (len > 0) {if (a[i] == b[j]) { // 如果a[i]和b[j]相同，则说明该字符在最长公共子序列中ans[len-1] = a[i];len--;i--;j--;} else { // 如果a[i]和b[j]不同，则说明f[i][j]是由f[i-1][j]和f[i][j-1]中较大的那个转移过来的if (f[i-1][j] > f[i][j-1]) {i--;} else {j--;}}}cout << ans << '\n'; // 输出最长公共子序列return 0;
}

记忆化搜索

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 2000; // 总预算
const int K = 6; // 商品数量
int p[K+1]; // 商品价格
int w[K+1]; // 商品重要度int dp[K+1][N+1];// 记忆化搜索函数
int dfs(int i, int j) {// 如果已经计算过当前状态，则直接返回结果if (dp[i][j] != -1) return dp[i][j];// 如果已经处理完所有商品或者总预算为0，则返回0if (i == 0 || j == 0) return dp[i][j] = 0;// 不选第i件商品int res = dfs(i-1, j);// 选第i件商品if (j >= p[i]) {res = max(res, dfs(i-1, j-p[i]) + p[i]*w[i]);}// 将结果存储在数组中以备后续使用return dp[i][j] = res;
}int main() {// 初始化dp数组为-1，表示当前状态还未计算过memset(dp, -1, sizeof(dp));// 输入商品价格和重要度for (int i = 1; i <= K; i++) {cin >> p[i] >> w[i];}// 输出最大价值cout << dfs(K, N) << endl;return 0;
}

题目三日常购物

3、日常购物

问题描述：小明今天很开心，因为在家买的新房子即将拿到钥匙。新房里面有一间他自己专用的、非常宽敞的房间。让他更高兴的是，他的母亲昨天对他说：“你的房间需要购买什么物品？怎么布置，你说了算，只要他们的价格总和不超过N元钱”。小明今天早上开始预算，但他想买太多的东西，肯定会超过母亲的N元限额。因此，他把对每件物品的渴望程度，分为5等级：用整数1->5表示，第5等表示最想要。他还从互联网上找到了每件商品（所有整数）的价格。他希望在不超过N元（可能等于N元）的情况下，将每件商品的价格与效益度的乘积的总和最大化.

设第j件物品的价格为p[j]，重要度为w[j]，其选中的k件商品，编号依次为j1，j2，……，jk，则所求的总和为：

p[j1]×w[j1]+p[j2]×w[j2]+ …+p[jk]×w[jk]。

请帮小明设计一个符合要求的购物清单。

其中N=2000,K=6

p[1]=200 w[1]=2

p[2]=300 w[2]=2

p[3]=600 w[3]=1

p[4]=400 w[4]=3

p[5]=1000 w[5]=4

p[6]=800 w[6]=5

朴素解法

#include <iostream>
#include <algorithm>
using namespace std;const int N = 2000; // 总预算
const int K = 6; // 商品数量
int p[K+1]; // 商品价格
int w[K+1]; // 商品重要度int dp[K+1][N+1];int main() {for (int i = 1; i <= K; i++) {cin >> p[i] >> w[i];}for (int i = 1; i <= K; i++) {for (int j = 1; j <= N; j++) {// 不选第i件商品dp[i][j] = dp[i-1][j];// 选第i件商品if (j >= p[i]) {dp[i][j] = max(dp[i][j], dp[i-1][j-p[i]] + p[i]*w[i]);}}}cout << dp[K][N] << endl;return 0;
}

记忆化搜索

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 2000; // 总预算
const int K = 6; // 商品数量
int p[K+1]; // 商品价格
int w[K+1]; // 商品重要度int dp[K+1][N+1];// 记忆化搜索函数
int dfs(int i, int j) {// 如果已经计算过当前状态，则直接返回结果if (dp[i][j] != -1) return dp[i][j];// 如果已经处理完所有商品或者总预算为0，则返回0if (i == 0 || j == 0) return dp[i][j] = 0;// 不选第i件商品int res = dfs(i-1, j);// 选第i件商品if (j >= p[i]) {res = max(res, dfs(i-1, j-p[i]) + p[i]*w[i]);}// 将结果存储在数组中以备后续使用return dp[i][j] = res;
}int main() {// 初始化dp数组为-1，表示当前状态还未计算过memset(dp, -1, sizeof(dp));// 输入商品价格和重要度for (int i = 1; i <= K; i++) {cin >> p[i] >> w[i];}// 输出最大价值cout << dfs(K, N) << endl;return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

23.4.21总结

23.4.21总结

正则表达式 正则表达式使用单个字符串来描述、匹配一系列匹配某个句法规则的字符串&#xff0c;通常被用来检索、替换那些符合某个模式&#xff08;规则&#xff09;的文本。 正则表达式是一种对字符串操作的一种逻辑公式&#xff0c;就是用事先定义好的一些特定字符、及这些…
阅读更多...
深度学习 - 42.特征交叉与 SetNET、Bilinear Interaction 与 FiBiNet

深度学习 - 42.特征交叉与 SetNET、Bilinear Interaction 与 FiBiNet

目录 一.引言 二.摘要 - ABSTRACT 三.介绍 - INTRODUCTION 四.相关工作 - RELATED WORK 1.因式分解机及其变体 - Factorization Machine and Its relevant variants 2. 基于深度学习的点击率模型 - Deep Learning based CTR Models 3.SENET Module 五.FiBiNet Model 1…
阅读更多...
【C++】哈希的应用：位图和布隆过滤器

【C++】哈希的应用：位图和布隆过滤器

目录 1. 位图1.1 位图的概念1.2 位图的结构1.3 位图的实现 2. 布隆过滤器2.1 概念2.2 结构2.3 布隆过滤器的实现 1. 位图 1.1 位图的概念 &#x1f4ad;位图&#xff08;bitset&#xff09;是一种基于哈希思想设计的数据结构&#xff0c;其功能主要用于判断数据是否已存在。适…
阅读更多...
来使用分支语句和循环语句实现一个小游戏吧（猜数字游戏）

来使用分支语句和循环语句实现一个小游戏吧（猜数字游戏）

猜数字游戏 1.代码展示2.菜单设计3.主函数部分3.随机数设计 所属专栏&#xff1a;C语言 博主首页&#xff1a;初阳785 代码托管&#xff1a;chuyang785 感谢大家的支持&#xff0c;您的点赞和关注是对我最大的支持&#xff01;&#xff01;&#xff01; 博主也会更加的努力&am…
阅读更多...
rtthread默认网卡的操作

rtthread默认网卡的操作

设置网卡优先级 在 RT-Thread 操作系统中&#xff0c;可以通过修改网卡的优先级来设置默认网卡。优先级越高的网卡会被优先选择为默认网卡。 下面介绍一些设置默认网卡优先级的方法&#xff1a; 在 RT-Thread 的网络配置文件 rtconfig.h 中&#xff0c;可以通过修改 NETIF_P…
阅读更多...
Jmeter5.1.1报错：java.net.BindException: Address already in use: connect

Jmeter5.1.1报错：java.net.BindException: Address already in use: connect

Jmeter5.1.1报错&#xff1a;java.net.BindException: Address already in use: connect 原因&#xff1a;从网上找到资料&#xff1a;端口占用 Windows提供给TCP/IP链接的端口为 1024-5000&#xff0c;并且要四分钟来循环回收它们&#xff0c;就导致我们在短时间内跑大量的请…
阅读更多...
把ChatGPT训练成你的得力助手

把ChatGPT训练成你的得力助手

在调教chatgpt时&#xff0c;我们大部分的时候都需要一个好的学术翻译官&#xff0c;但是在他成为学术翻译官之前我们有很多规定要说明&#xff0c;比如不用回答我的问题&#xff0c;不用计算公式等。我将以下命令要求集成&#xff0c;在使用的时候只需要你发给它这段话&#x…
阅读更多...
如何评估小程序开发费用：从项目规模到技术需求

如何评估小程序开发费用：从项目规模到技术需求

作为一种越来越受欢迎的移动应用&#xff0c;小程序的开发费用是许多企业和个人考虑的重要因素之一。但是&#xff0c;要确定小程序开发费用并不是一件容易的事情&#xff0c;因为它涉及到多个因素&#xff0c;从项目规模到技术需求。 项目规模 小程序开发的费用通常与项目规…
阅读更多...
Linux部署人大金仓(Kingbase8)

Linux部署人大金仓(Kingbase8)

陈老老老板&#x1f9b8; &#x1f468;‍&#x1f4bb;本文专栏&#xff1a;国产数据库-人大金仓&#xff08;kingbase8&#xff09;&#xff08;主要讲一些人大金仓数据库相关的内容&#xff09; &#x1f468;‍&#x1f4bb;本文简述&#xff1a;本文讲一下LInux上部署人大…
阅读更多...
Vue+Echarts 项目演练（中）后台数据接口的创建

Vue+Echarts 项目演练（中）后台数据接口的创建

全局引用Echarts与axios 后台接口创建express路由 api接口数据创建 全局引用Echarts与axios vue3.0的挂载方式&#xff1a;使用Provide/Inject依赖注入&#xff0c;将替代vue2中在原型链上挂载一些属性在app.vue中使用provider来给后代们提供数据 <script> import { p…
阅读更多...
经典数据结构之2-3树

经典数据结构之2-3树

2-3树定义 2-3树&#xff0c;是最简单的B-树&#xff0c;其中2、3主要体现在每个非叶子节点都有2个或3个子节点&#xff0c;B-树即是平衡树&#xff0c;平衡树是为了解决不平衡树查询效率问题&#xff0c;常见的二叉平衡书有AVL树&#xff0c;它虽然提高了查询效率&#xff0c…
阅读更多...
深入JVM了解Java对象实例化过程

深入JVM了解Java对象实例化过程

文章目录 一、对象创建方式二、对象产生步骤1、判断对象是否已经加载、链接、初始化2、为对象分配内存空间3、处理并发问题3.1 TLAB 4、初始化零值5、完善对象内存布局的信息6、调用对象的实例化方法 <init>7、总结 三、对象的内存布局1、对象头1.1 运行时元数据&#xf…
阅读更多...
详解树与二叉树的概念，结构，及实现（上篇）

详解树与二叉树的概念，结构，及实现（上篇）

目录 一&#xff0c; 树 1.2 树的相关概念 1.3 树的表示 1.4 树在实际中的运用&#xff08;表示文件系统的目录树结构&#xff09; 二&#xff0c; 二叉树 2.1二叉树概念 三&#xff0c;特殊的二叉树 1. 满二叉树 2. 完全二叉树 3. 1 二叉树的性质 3. 2 二叉树的存储…
阅读更多...
【速卖通】 AliExpress(速卖通)关键词搜索结果采集

【速卖通】 AliExpress(速卖通)关键词搜索结果采集

采集场景 在AliExpress(速卖通) 首页中 http://www.aliexpress.com 中输入关键词&#xff0c;采集关键词搜索后得到的商品列表信息。 采集字段 关键词、标题、商品id、商品图片地址、商品详情链接、价格、免费退送货、星级、已出售数量、店铺名 采集结果 采集结果可导出为E…
阅读更多...
Linux-初学者系列——篇幅7_文本编辑和处理命令

Linux-初学者系列——篇幅7_文本编辑和处理命令

文本编辑和处理命令-目录 一、系统基本编辑命令安装vim软件工具包语法格式&#xff1a; 1、vim编辑命令模式01 普通模式02 编辑模式03 命令模式 2、编辑文件技巧01 批量删除多行指定信息02 批量增加多列指定信息03 编辑常见问题错误1&#xff1a;没有指定编辑信息错误2&#xf…
阅读更多...
基于TensorRT的yolov5 实例分割部署

基于TensorRT的yolov5 实例分割部署

yolov5-7.0 github: https://github.com/ultralytics/yolov5/tree/master 1. 代码的使用 1.1 训练yolov5-seg模型 使用的yolov5-7.0的代码，github下载：https://github.com/ultralytics/yolov5/releases/tag/v7.0 训练指令 python segment/train.py --data coco128-seg.y…
阅读更多...
centos7 查看服务器配置信息

centos7 查看服务器配置信息

1.linux查看版本当前操作系统发行信息 cat /etc/centos-release cat /etc/centos-release 2、查看内核版本uname -a或者cat /proc/version 3、查看CPU参数 1&#xff09;、查看 CPU 物理个数 　　grep physical id /proc/cpuinfo | sort -u | wc -l 2&#xff09;、查看 CPU …
阅读更多...
SpringCloud：ElasticSearch之DSL查询文档

SpringCloud：ElasticSearch之DSL查询文档

elasticsearch的查询依然是基于JSON风格的DSL来实现的。 1.1.DSL查询分类 Elasticsearch提供了基于JSON的DSL&#xff08;Domain Specific Language&#xff09;来定义查询。常见的查询类型包括&#xff1a; 查询所有&#xff1a;查询出所有数据&#xff0c;一般测试用。例如…
阅读更多...
magento webapi 接口返回 json对象

magento webapi 接口返回 json对象

前言 现在主流的项目开发都是前后端分离&#xff0c;数据通过json对象格式进行传输。但是magento框架&#xff0c;和传统PHP框架相比&#xff0c;区别很大。虽然也支持以RestApi的形式传输数据&#xff0c;但是要么格式并非是传统jsonObject要么就是需要大量的get、set方法。本…
阅读更多...
关于xilinx使用PCIE实现FPGA的部分重配置实现(MCAP)

关于xilinx使用PCIE实现FPGA的部分重配置实现(MCAP)

平台&#xff1a;vivado21018.3 芯片&#xff1a;xcku115-flva1517-2-i (active) 本文官方文档&#xff1a;Xilinx_Answer_64761_Ultrascale_Devices 本文驱动下载地址&#xff1a;64761 - Bitstream Loading across the PCI Express Link in UltraScale and UltraScale Dev…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023