5.动态规划

1.背包问题

(1)0/1背包问题

        01背包问题即每个物品只能选1个

        考虑第i件物品,当j<w[i]时,f[i][j]=f[i-1][j],当j>=w[i]时,此时有两种选择,选择第i件物品和不选第i件物品。此时f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])

        有 n件物品和一个容量是m的背包。每件物品只能使用一次,第i件物品的体积是vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大.输出最大价值。 

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1010;
int w[N],v[N];
int f[N][N];int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j] = f[i-1][j];if(j>=w[i]) f[i][j] = max(f[i][j],f[i-1][j-w[i]]+v[i]);} }printf("%d",f[n][m]);return 0;}

 (2)完全背包问题

        完全背包问题即物品可以选多个

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1010;
int w[N],v[N];
int f[N][N];int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j] = f[i-1][j];  // 注意选择物品下标为i,区别于01背包if(j>=w[i]) f[i][j] = max(f[i][j],f[i][j-w[i]]+v[i]);}}printf("%d",f[n][m]);return 0;}

 (3) 多重背包问题

        多重背包问题可以转化为0-1背包问题进行优化。假设第i个物品可选c个,那么我们可以用二进制组合为0-c范围的数。此时,每一位二进制可视为一件物品。

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1e3+10;
const int V = 110;
int f[N][V];
int v[N],w[N];
int cnt = 0;int main(){int n,m;scanf("%d%d",&n,&m);int a,b,c,k;while (n--){scanf("%d%d%d",&a,&b,&c);k = 1;while (k<=c)  // 将c用二进制进行拆分{cnt++;w[cnt] = k*a;v[cnt] = k*b;c -= k;k *=2;}if(c){  // 拆分为二进制后的剩余部分cnt++;w[cnt] = c * a;v[cnt] = c*b;}}for(int i=1;i<=cnt;i++) // 当成0-1背包问题求解for(int j=1;j<=m;j++){f[i][j]=f[i-1][j];if(j>=w[i]) f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);}printf("%d",f[cnt][m]);return 0;}

(3)分组背包问题

        分组背包问题只需要考虑每一组选择某个物品的最大价值,只需要加一层循环。

#include <iostream>
#include <algorithm>
using namespace std;const int N = 110;
const int V = 110;
const int S = 110;int f[N][V];  // DP表
int w[N][S];  // 重量
int v[N][S];  // 价值
int G[N];     // 每一组物品种类数int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&G[i]); for(int j=1;j<=G[i];j++)scanf("%d%d",&w[i][j],&v[i][j]);}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i][j] = f[i-1][j];for(int k=1;k<=G[i];k++){ // 遍历每一组if(j>=w[i][k]) f[i][j] = max(f[i][j],f[i-1][j-w[i][k]]+v[i][k]);}}printf("%d",f[n][m]);return 0;
}

2.线性DP

     (1)数字三角形

        给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。

    算法思想:对于每一个i,j,都有两条路径,即从左到右的一条与从左上角到右的一条。因此

f[i][j]=max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j])

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 510;
const int inf = 1e9;
int a[N][N];
int f[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=0;i<=n;i++)  // 初始化矩阵for(int j=0;j<=n;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 res = -inf;for(int i=1;i<=n;i++)res = max(f[n][i],res);printf("%d",res);return 0;
}

 (2) 最长上升子序列

        给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少

        对于每一个f[i],如果前面有更小的数,f[i]=max(f[i],f[j]+1)。

#include <iostream>
using namespace std;const int N = 1010;
int a[N],f[N];int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){f[i] = 1;   // a[i]前面没有最小的数for(int j=1;j<i;j++) // 如果a[i]前面有更小的数,则更新if(a[j]<a[i]) f[i] = max(f[i],f[j]+1);}int res = 0;for(int i=1;i<=n;i++) res = max(res,f[i]);printf("%d",res);return 0;
}

 (3)最长公共子序列

        当匹配到A[i]和B[j]时,有4种情况,如下图所示

        其中,第一种情况包含在第2,3种情况中,第4种情况需要A[i]与B[j]匹配成功

给定两个长度分别为 N 和 M 的字符串 和 B,求既是 A的子序列又是 B 的子序列的字符长度最长是多少
输入格式
第一行包含两个整数 N和 M
第二行包含一个长度为 N的字符串,表示字符串 A
第三行包含一个长度为 M 的字符串,表示字符串 B
字符串均由小写字母构成。 

#include <iostream>
#include <cstring>
using namespace std;const int N = 1010;
const int M = 1010;
char A[N],B[M];
int f[N][M];int main(){int n,m;scanf("%d%d",&n,&m);scanf("%s%s",A+1,B+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i][j] = max(f[i-1][j],f[i][j-1]); // 子串A[i-1]与B[j]匹配或者A[i]与B[j-1]匹配if(A[i]==B[j]) f[i][j] = max(f[i][j],f[i-1][j-1]+1); // 子串A[i]与B[j]匹配且匹配成功}printf("%d",f[n][m]);
}

(4)最短编辑距离

增删改情况如下图

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1010;
const int M = 1010;
char A[N],B[M];
int f[N][M];int main(){int n,m;scanf("%d%s",&n,A+1);scanf("%d%s",&m,B+1);for(int i=0;i<=n;i++) f[i][0] = i; // 边界条件,初始化for(int j=0;j<=m;j++) f[0][j] = j;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1); // 增与删if(A[i]==B[j]) f[i][j] = min(f[i][j],f[i-1][j-1]); // A[i]与B[j]匹配成功else f[i][j] = min(f[i][j],f[i-1][j-1]+1);  // A[i]与B[j]匹配不成功}printf("%d",f[n][m]);return 0;
}

应用:

给定 n 个长度不超过 10 的字符串以及 m 次询问,每次问给出一个字符串和一个操作次数上限.
对于每次询问,请你求出给定的n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

算法思想:多次求编辑距离

#include <iostream>
#include <algorithm>
#include <string.h>using namespace std;const int N = 1010;
int f[15][15];
char str[N][15];int edit_dist(char a[],char b[]){int la = strlen(a+1);int lb = strlen(b+1);for(int i=0;i<=la;i++) f[i][0] = i;  // 边界情况for(int i=0;i<=lb;i++) f[0][i] = i;for(int i=1;i<=la;i++)for(int j=1;j<=lb;j++){f[i][j] = min(f[i][j-1]+1,f[i-1][j]+1);  // 增和删if(a[i]==b[j]) f[i][j] = min(f[i][j],f[i-1][j-1]); // 匹配成功else f[i][j] = min(f[i][j],f[i-1][j-1]+1);  // 改}return f[la][lb];
}int main(){int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++) scanf("%s",str[i]+1);int limit,res;while (m--){char s[15];scanf("%s%d",s+1,&limit);res = 0;for(int i=0;i<n;i++)if(edit_dist(str[i],s)<=limit) res++;printf("%d\n",res);}return 0;
}

 3.区间类DP

        石子合并:

算法思想:动态规划加分治法。对于区间[L,R],可以从第k个位置分开,合并的代价包含三部分:

(1)合并左侧;(2)合并右侧;(3) 将左右部分合并;k的位置从[l,r]。取代价最小值。

即f[l][r]=min(f[i][k]+f[k+1][r]+s[r]-s[l-1])。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 310;
int s[N];  // 前缀和数组
int f[N][N]; // 递推数组int main(){int n;    // 石子堆数scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&s[i]);for(int i=1;i<=n;i++) s[i] = s[i]+s[i-1];int l,r;for(int len=2;len<=n;len++)for(int i=1;i+len-1<=n;i++){l = i,r=i+len-1;f[l][r] = 1e8;for(int k=l;k<r;k++)  // 最后一次合并从节点k将区间分为两部分f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);}printf("%d",f[1][n]);return 0;
}

4.整数划分

算法思想:整数划分可以采用完全背包问题解决,当j<i时,不能选i,此时f[i][j]=f[i-1][j],当j>=i时,f[i][j] = f[i-1][j] + f[i][j-i](注意此时求的是方案数)

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1010;
const int M = 1e9+7;
int f[N][N];int main(){int n;scanf("%d",&n);for(int i=0;i<=n;i++)f[i][0] = 1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){f[i][j] = f[i-1][j];  // j<i,不能选iif(j>=i)  // j>i,可以选if[i][j] = (f[i-1][j] + f[i][j-i]) % M;}printf("%d",f[n][n]);return 0;
}

5.状态压缩DP 

多米诺骨牌问题

首先,如果全部用横条填充完整个棋盘,剩下的用竖条填充,方案是确定的。

使用二进制表示每一列的填充情况。当第i-1与第i列两列没有被横向网格填充,且存在两个连续的网格接收横向网格,则填充。此时:f[i][j] += f[i-1][k]。即累加第i-1行的填充结果

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 12, M = 1 << N;int n, m;
long long f[N][M];
bool st[M];int main()
{while (1){scanf("%d%d",&n,&m);if(n ==0 || m==0) break;for(int i=0;i< 1<<n;i++){int cnt = 0;st[i] = 1;for(int j=0;j<n;j++)if(i >>j &1){     // 该位为1if(cnt & 1) st[i] = 0;  // 连续奇数个1cnt = 0;}else cnt++;    // 连续0的个数if(cnt & 1) st[i] = 0;  // 最后有奇数个1}memset(f, 0, sizeof f);memset(f, 0, sizeof f);f[0][0] = 1; // 一种方案,不填for(int i=1;i<=m;i++)for(int j=0;j< 1<<n; j++)for(int k=0;k< 1<<n; k++)if((j & k)==0 && st[j|k]) f[i][j] += f[i-1][k]; // 意味着没有一列是两行都被填充的且能够找到两列都没有被填充的cout << f[m][0] << endl;}return 0;
}

哈密尔顿通路:

给定一张n 个点的带权无向图,点从0~ n -1标号,求起点0到终点n -1的最短 Hamilton 路径
Hamilton 路径的定义是从 0 到 n-1不重不漏地经过每个点恰好一次。

算法思想:基于动态规划的思想,对于每一次的f[i][j],表示j为当前最后一次经过的节点,首先,要走遍子集i中除去j以外的所有节点,到达节点k,然后再从第k个节点到达第j个节点,即f[i][j]=min(f[i-{j}][k]+w[k][j])

#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;const int N = 20;
const int M = 1 << N;
int G[N][N];
int f[M][N];int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&G[i][j]);memset(f,0x3f,sizeof f);f[1][0] = 0;   // 从0号点经过0号点到0for(int i=0;i< 1<<n;i++)  // 用二进制表示当前节点子集for(int j=0;j<n;j++){if(i>>j & 1)   // 当前子集包含第j个节点for(int k=0;k<n;k++)if(i>>k &1)  // 子集i中包含节点kf[i][j] = min(f[i][j],f[i-(1<<j)][k]+G[k][j]);}printf("%d",f[(1<<n)-1][n-1]);return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

【QingHub】QingHub Studio企业级应用作业编排

简介 QingHub作业编排中心是一个通过插件化方式&#xff0c;提供数据从采集&#xff0c;转化&#xff0c;计算&#xff0c;存储为一体的全流程数据处理方案&#xff0c;他一方面为前端应用提供数据源&#xff0c;同时也为前端应用与数据源头的通信搭建起桥梁&#xff0c;实现数…

【WebKit架构讲解】

&#x1f308;个人主页:程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

C++:函数重载,引用

文章目录 1. 函数重载1.1 函数重载概念1.2 C支持函数重载的原理--名字修饰1.3 缺省参数与重载 2. 引用2.1引用概念2.2 引用特性2.3 常引用2.4 使用场景2.5 引用和指针的区别 1. 函数重载 1.1 函数重载概念 C允许在同一作用域中声明几个功能类似的同名函数&#xff0c;这些同名…

查看并设定【网络适配器】的优先级(跃点数)

目录 前言&#xff1a; 1.查看所有的适配器 2.修改优先级&#xff08;需要以管理员身份运行&#xff09; 跃点数&#xff08;InterfaceMetric &#xff09; DHCP 3.修改后的效果 pwoerShell 再次运行之前的程序 4.其他 参考 网络适配器1&#xff0c;8相关知识介绍1 …

回溯算法|47.全排列II

力扣题目链接 class Solution { private:vector<vector<int>> result;vector<int> path;void backtracking (vector<int>& nums, vector<bool>& used) {// 此时说明找到了一组if (path.size() nums.size()) {result.push_back(path);r…

【前端】CSS(引入方式+选择器+常用元素属性+盒模型)

文章目录 CSS一、什么是CSS二、语法规范三、引入方式1.内部样式表2.行内样式表3.外部样式 四、选择器1.选择器的种类1.基础选择器&#xff1a;单个选择器构成的1.标签选择器2.类选择器3.id 选择器4.通配符选择器 2.复合选择器1.后代选择器2.子选择器3.并集选择器4.伪类选择器 五…

python基于django协同算法的个性化音乐推荐系统的设计与实现

本个性化音乐推荐系统以Django作为框架&#xff0c;b/s模式以及MySql作为后台运行的数据库。本系统主要包括以下功能模块&#xff1a;首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;歌曲类型管理&#xff0c;明星歌手管理&#xff0c;歌曲音乐管理&#xff0c;歌曲…

Java基于微信小程序的电子竞技信息交流系统,附源码(V2.0)

博主介绍&#xff1a;✌IT徐师兄、7年大厂程序员经历。全网粉丝15W、csdn博客专家、掘金/华为云//InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3…

AI预测福彩3D第24弹【2024年4月2日预测--第6套算法开始计算第1次测试】

今天&#xff0c;咱们进行第6套算法测试&#xff0c;本套算法将结合012路直选共27种组合&#xff0c;同时考虑了对012路的和值进行统计分析。今天为第1次测试&#xff0c;好了&#xff0c;废话不多说了。直接上结果~ 仍旧是分为两个方案&#xff0c;1大1小。 经过人工神经网络计…

常用的限流方案思路和实现

限流方案 1、计数器&#xff08;固定窗口&#xff09; 1.1、简介 计数器固定窗口算法是最基础也是最简单的一种限流算法。原理就是对一段固定时间窗口内的请求进行计数&#xff0c;如果请求数超过了阈值&#xff0c;则舍弃该请求&#xff1b;如果没有达到设定的阈值&#xf…

【单点登录SSO,Auth2,jwt-过程分析】

目录 单点登录简介 SSO&CAS是什么 单点登录适合什么场景 单点登录的三种实现方式 CAS的几个重要知识点 CAS的实现过程 单点登录简介 单点登录(SingleSignOn&#xff0c;SSO)&#xff0c;就是通过用户的一次性鉴别登录。当用户在身份认证服务器上登录一次以后&#xff0c;即…

C++ //练习 11.12 编写程序,读入string和int的序列,将每个string和int存入一个pair中,pair保存在一个vector中。

C Primer&#xff08;第5版&#xff09; 练习 11.12 练习 11.12 编写程序&#xff0c;读入string和int的序列&#xff0c;将每个string和int存入一个pair中&#xff0c;pair保存在一个vector中。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#x…

【JavaWeb】Day32.MySQL概述

什么是数据库 数据库&#xff1a;英文为 DataBase&#xff0c;简称DB&#xff0c;它是存储和管理数据的仓库。 像我们日常访问的电商网站京东&#xff0c;企业内部的管理系统OA、ERP、CRM这类的系统&#xff0c;以及大家每天都会刷的头条、抖音类的app&#xff0c;那这些大家所…

苍穹外卖Day04套餐管理部分总结

写给像我一样完完全全的小白的。本人代码水平一塌糊涂&#xff0c;前几天就是机械地跟着视频敲代码。对于Day04的作业本来感觉代码抓瞎一点不会写&#xff0c;尽力去理解业务逻辑后发现好像也没那么难&#xff0c;整体代码可以仿照Day03新增菜品来进行实现&#xff01; 一、功…

面试复盘1 - 测试相关(实习)

写在前&#xff1a;hello&#xff0c;大家早中晚上好~这里是西西&#xff0c;最近有在准备测试相关的面试&#xff0c;特此开设了新的篇章&#xff0c;针对于面试中的问题来做一下复盘&#xff0c;会把我自己遇到的问题进行整理&#xff0c;除此之外还会进行对一些常见面试题的…

6.S081的Lab学习——Lab2: system calls

文章目录 前言一、System call tracing&#xff08;moderate&#xff09;解析&#xff1a; 二、Sysinfo&#xff08;moderate&#xff09;解析&#xff1a; 前言 一个本硕双非的小菜鸡&#xff0c;备战24年秋招。打算尝试6.S081&#xff0c;将它的Lab逐一实现&#xff0c;并记…

人工智能上手 Pytorch

人工智能上手 Pytorch 1、人工智能框架历史走向 2015年&#xff0c; caffe&#xff0c;优势配置简单&#xff0c;缺点安装麻烦&#xff0c;且不更新维护 2016年&#xff0c;tensorflow 1.x&#xff0c;定义太严格&#xff0c;很复杂。开发成本高。简单的任务&#xff0c;也很…

今客CRM客户管理系统 v17.3

简介&#xff1a; 今客CRM客户管理系统主要是为了帮助企业解决在日常工作中遇到的客户管理等难题而开发&#xff0c;通过今客CRM客户管理系统可以对企业事务中的不同功能进行操作&#xff0c;用户通过自定义字段类型可以达到适合不同企业的需求。在今客客户关系管理系统中管理…

来个自定义的电子木鱼吧

<!DOCTYPE html> <html><head><meta charset"utf-8"><meta name"viewport" content"widthdevice-width, initial-scale1"><title>自定义木鱼</title> </head> <body style"background-…

Rredis缓存常见面试题

文章目录 1.什么是缓存穿透&#xff0c;怎么解决2.什么是缓存击穿&#xff0c;怎么解决3.什么是缓存雪崩&#xff0c;怎么解决4.双写一致性问题5.redisson添加的排他锁是如何保证读写、读读互斥的6.为什么不使用延迟双删7.redis做为缓存&#xff0c;数据的持久化是怎么做的8.re…