首页 > 其他分享 >动态规划(有背包问题)

动态规划(有背包问题)

时间:2024-09-28 16:22:22浏览次数:10  
标签:背包 int cin long 道题 1005 动态 规划 dp

目录

1.动态规划的介绍

2.动态规划的例题

第1道题 数字三角形

(如果想看递归写法可以到我的记忆化递归里去看看记忆化递归_将递归程序记忆化-CSDN博客)

第2道题最长公共子序列(模板) 

第3道题 最长上升子序列

第4道题最大子段和

背包系列问题

01背包

完全背包


1.动态规划的介绍

是解决多阶段决策问题常用的最优化理论,该理论由美国数学家Bellman等人在1957年提出,用于研究多阶段决策过程的优化问题。


动态规划方法的原理就是把多阶段决策过程转化为一系列的单阶段决策问题,利用各个阶段之间的递推关系,逐个确定每个阶段的最优化决策,最终堆看出多阶段决策的最优化决策结果。


动态规划适合求解多阶段(状态转换)决策问题的最优解,决策的阶段可以随时间划分也可以随着问题的演化状态划分。问题都具有的一个性质就是“最优子结构”。

而动态规划的重点就是在于找出状态转移方程。

接下来我们看几道例题

2.动态规划的例题

第1道题 数字三角形

(如果想看递归写法可以到我的记忆化递归里去看看记忆化递归_将递归程序记忆化-CSDN博客)

数字三角形的洛谷链接:[USACO1.5] [IOI1994]数字三角形 Number Triangles - 洛谷

这道题问的就是怎样走可以数字和最大(一棵树);

这道题思路很简单,我们可以从这棵树的底部开始进行运算,比大小。

所以我们的动态转移方程就是:d[i][j] = a[i][j]+max(d[i+1][j],d[i+1][j+1]);//它等于它底下的节点中的最大值加上本身

最后代码:

#include <bits/stdc++.h>
using namespace std;
int d[1005][1005];
int a[1005][1005];
int n;
int main(){
    cin >> n;
    for (int i =1; i <= n+1; i++){
        for (int j =1; j <= i; j++){
            cin >> a[i][j];
        }
    }
    for (int j =1; j <= n; j++){
        d[n][j] = a[n][j];
    }
    for (int i =n-1; i >= 1; i--){
        for (int j =1; j <= i; j++){
            d[i][j] = a[i][j]+max(d[i+1][j],d[i+1][j+1]);
        }
    }
    cout << d[1][1];
    return 0;
}

第2道题最长公共子序列(模板) 

注意子序列是不连续的(也可以连续,但不强求连续)

这道题思路并不是那么难;, A、B,2个字符串每一号位进行比较,如果它们这两个字符相等的话,我们就要让dp[i][j]=dp[i-1][j-1]+1,其中+1代表增加了一个公共子序列中的字符,然后再加上没有它们两个字符的时候的值。如果这两个字符不相等,那就取不包含第一个字符和不包含第二个字符的最长子序列最大值(长度)。

所以我们可以得出的状态转移公式:

if (a[i-1] == b[j-1]){
	dp[i][j] = dp[i-1][j-1]+1;         
}
else{
	dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
}

总体代码:

#include <bits/stdc++.h>
using namespace std;
int dp[10000][10000];
int main(){
    int n ,m;
    cin >> n >> m;
    string a,b;
    cin >> a >> b;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (a[i-1] == b[j-1]){
				dp[i][j] = dp[i-1][j-1]+1;
                
            }
            else{
				dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
               
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

第3道题 最长上升子序列

 最长上升子序列 - 洛谷

上面是洛谷的链接⬆️

这道题的总体思路:

dp[i]的意思是从0号位到i号位最长上升子序列(子序列的结尾是i号位)

进行循环构建出DP数组

状态转移公式:


            if (a[j] < a[i]){
                dp[i] = max(dp[i],dp[j]+1);
            }

最后再用M算出整个数组中的最大值.

最后代码:

#include <bits/stdc++.h>
using namespace std;
int dp[50000];
int a[100000];
int main(){
	int n; 
    cin >> n;
    for (int i = 0; i <n; i++){
        cin >> a[i];
    }
    int m = 0;
    for (int i = 0; i <n; i++){
        dp[i] = 1;
        for (int j = 0; j <i; j++){
            if (a[j] < a[i]){
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
        if (dp[i] > m){
            m = dp[i];
        }
    }
    cout << m;
    return 0;
}

第4道题最大子段和

( ̄y▽ ̄)╭最大子段和 - 洛谷

这道题的思路很简单,dp[i]代表着从0号位到第i号位结尾为第i号位的最大子段和是多少

那就可以分为(取前面的和)和(不取前面的和)

在求一个最大值中的最大值就OK了

状态转移公式:


        dp[i] = max(dp[i-1]+a[i],a[i]);

总体代码:

#include <bits/stdc++.h>
using namespace std;
long long dp[500005];
long long a[500000];
int main(){
	int n; 
    cin >> n;
    for (int i = 0; i <n; i++){
        cin >> a[i];
    }
    long long m = -2e9;
    for (int i = 0; i <n; i++){
        dp[i] = max(dp[i-1]+a[i],a[i]);
        m = max(m,dp[i]);
    }
    
    cout << m;
    return 0;
}

背包系列问题

01背包

0< N,M ≤1000

0< vi,pi ≤1000

我们可以分成几种情况

 dp[i][j]代表了1~i个东西和可装重量为j的书包

dp[i-1][j-v[i]]代表了如果总重量加入了我们第i个物品(也就是放了),最终可以得到多少价值的东西.

转移公式:

if (j < v[i]){
    dp[i][j] = dp[i-1][j];
}
else{
    dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
}

最后代码:

#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main(){
    int n,m;
    cin >> n >> m;
    int v[1005],w[1005];
    for (int i = 1; i <= n; i++){
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (j < v[i]){
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

完全背包

疯狂的采药:疯狂的采药 - 洛谷

完全背包和01背包的不同在于一个东西它可以有无限个,也就是说你可以取无限次,只要你背包还有容量那我们就要把i-1改成i因为这一个东西它可以取很多次.

在这里我们用的是一维数组,我们要倒过来循环

转移方程:(只不过这里的写法不同,和上面的判断条件意思是一样的)


            dp[j]= dp[j];
            if (j >= w[i]){
                dp[j] = max(dp[j],dp[j-w[i]]+c[i]);
            }

 所有代码:

#include <bits/stdc++.h>
using namespace std;
long long w[10000005],c[10000005];
long long dp[10000005];
long long m,n;
int main(){
    cin >> m >>n;
    for (long long i = 1; i <= n; i++){
        cin >> w[i] >> c[i];
        for (long long j = 1; j <= m; j++){
            dp[j]= dp[j];
            if (j >= w[i]){
                dp[j] = max(dp[j],dp[j-w[i]]+c[i]);
            }
        }
    }
    
    cout << dp[m];
    return 0;
}

标签:背包,int,cin,long,道题,1005,动态,规划,dp
From: https://blog.csdn.net/pythonwyw123321/article/details/142615273

相关文章

  • [题目记录]一本通高手训练-01背包
    题意有\(n\)个物品,每个物品体积为\(s_i\),价值为\(v_i\),求背包容量为\(1,2,\cdotsm\)时最大价值.\(n\le1e6,m\le1e5,s\le300,v\le1e9\)时空限制\(5s,512MB\)题解普通01背包复杂度\(O(nm)\),无法满足\(n\le1e6,m\le1e5\).发现\(s\le300\),可以考虑......
  • Leetcode 1235. 规划兼职工作
    1.题目基本信息1.1.题目描述你打算利用空闲时间来做兼职工作赚些零花钱。这里有n份兼职工作,每份工作预计从startTime[i]开始到endTime[i]结束,报酬为profit[i]。给你一份兼职工作表,包含开始时间startTime,结束时间endTime和预计报酬profit三个数组,请你计算并返回可......
  • 基于冲突动态监测算法的健身房预约管理系统
    系统展示用户前台界面管理员后台界面系统背景  随着健身热潮的兴起,健身房管理面临着日益增长的会员需求与资源分配的挑战。传统的人工预约方式不仅效率低下,且容易出现时间冲突和资源浪费的情况。为了解决这一问题,基于冲突动态监测算法的健身房预约管理系统......
  • MyBatis 动态语句
    一、if和where语句<!--List<Employee>selectEmployeeByCondition(Employeeemployee);--><selectid="selectEmployeeByCondition"resultType="employee">selectemp_id,emp_name,emp_salaryfromt_emp<!--where标签会......
  • C#爬取动态网页上的信息:B站主页
    目录简介获取HTML文档解析HTML文档测试参考文章简介动态内容网站使用JavaScript脚本动态检索和渲染数据,爬取信息时需要模拟浏览器行为,否则获取到的源码基本是空的。爬取步骤如下:使用Selenium获取渲染后的HTML文档使用HtmlAgilityPack解析HTML文档新建项目,安......
  • 全球切削用涂层带锯条市场规划预测:未来六年CAGR为3.1%
    本文深入分析了切削用涂层带锯条市场的发展趋势、投资机会与挑战。通过对行业增长点、风险评估及未来展望的探讨,结合恒州诚思研究的数据洞察,为投资者提供了宝贵的信息和策略建议。一、引言切削用涂层带锯条作为现代制造业中不可或缺的工具之一,其性能直接影响到加工效率和产品质......
  • 网络安全自学入门:(超详细)从入门到精通学习路线&规划,学完即可就业
     很多人上来就说想学习黑客,但是连方向都没搞清楚就开始学习,最终也只是会无疾而终!黑客是一个大的概念,里面包含了许多方向,不同的方向需要学习的内容也不一样。算上从学校开始学习,已经在网安这条路上走了10年了,无论是以前在学校做安全研究,还是毕业后在百度、360从事内核安全产......
  • 解锁微信小程序新技能:ECharts动态折线图搭配WebSocket,数据刷新快人一步!
    在微信小程序中,数据可视化展示越来越受到开发者的重视。本文将为您介绍如何在微信小程序中使用ECharts绘制折线图,并通过WebSocket实现实时更新图表数据。一、准备工作创建微信小程序项目 首先,我们需要创建一个微信小程序项目。如果您已经熟悉如何创建项目,可以跳过此步骤。......
  • RIP与动态BFD联动
    概述通常情况下,RIP通过定时接收和发送更新报文来保持邻居关系,在老化定时器时间内没有收到邻居发送的更新报文则宣告邻居状态变为Down。老化定时器的缺省值为180s,如果出现链路故障,RIP要经过180s才会检测到。如果网络中部署了高速数据业务,在此期间将导致数据大量丢失。BFD能够提......
  • NestJS实战-产品需求规划
    NestJS实战-产品需求规划本文介绍NestJS实战的产品需求规划,介绍前后端技术栈、对业务需求模块进行功能规划、系统环境详细搭建和数据库表结构简单设计。供自己以后查漏补缺,也欢迎同道朋友交流学习。引言之前写了有关Node和NestJS相关知识点的文章,但有些模块介绍的......