数据结构与算法之动态规划算法(DP)

文章目录

  • 前言
  • 1.0-1背包问题
    • 1.1 基本概念
    • 1.2 具体问题
    • 1.3 c代码求解
    • 1.4 测试
  • 2.最长公共子序列

前言

前边我们讲过分治法,分治法的核心是将一个问题分解为n个小问题,最后合并结果。而动态规划算法的核心是穷举法,以及要寻找到一个状态方程,需要用一个DP表或者函数来记录穷举的结果,从穷举过程中选择最优的值,最后得到原始问题的解

1.0-1背包问题

1.1 基本概念

完全背包问题是背包问题的一种变种,与 0-1 背包问题不同的是,每个物品可以无限次选择放入背包,即可重复使用。动态规划是解决完全背包问题的常用方法。

1.2 具体问题

有n个物品,每个物品的价值为Vi,重量为Wi,背包的容量为C,现在需要将n个物品放入背包,总重量不能超过背包的容量,使得装入的物品的价值达到最大。
求解的问题:放入背包的价值最大
约 束 条 件:重量之和不能超过背包的容量。

实际例子: 假设物品的个数为5个,背包的容量为20,物品的价值和重量如下:

物品编号12345
价值v45101215
重量w347912

简单的例子我们可以穷举下:
1.20=4+7+9 此时的价值为: 5+10+12=27
2.19=7+12 此时的价值为:10+15 =25
…等等

1.3 c代码求解

/*** 0-1 背包问题* @param n 物品的个数* @param c 背包的容量* @param w 物品的重量数组* @param v 物品的价值数组* @return dp表*/
int ** KnapsackDp(int n,int c,int *w,int *v,int ** path){int i,tempc;//定义一个二维的数组dp表int ** dp = (int **)malloc(sizeof (int*)*(n+1));for(int i=0;i<=n;i++){dp[i]= (int *)malloc(sizeof (int )*(c+1));}//由于下标是从0开始初始化第一行for(tempc = 0;tempc <= c ;tempc ++){dp[0][tempc]=0;path[0][tempc]=0;}for(i = 1;i <= n ;i ++){dp[i][0]=0;path[i][0]=0;//开始动态for(tempc = 1 ; tempc <= c ; tempc++){path[i][tempc]=0;if( w[i-1] <= tempc){//背包的剩余重量大于物品重量if(v[i-1]+dp[i-1][tempc-w[i-1]] > dp[i-1][tempc]){//放入背包dp[i][tempc]=v[i-1]+dp[i-1][tempc-w[i-1]];path[i][tempc]=1;}else{dp[i][tempc]=dp[i-1][tempc];}}else{dp[i][tempc]=dp[i-1][tempc];}}}return dp;
}

1.4 测试

int main(){int n=5;int c=20;int w[]={3,4,7,9,12};int v[]={4,5,10,12,15};//记录是否放入int ** path = (int **)malloc(sizeof (int*)*(n+1));for(int i=0;i<=n;i++){path[i]= (int *)malloc(sizeof (int )*(c+1));}int **dp = KnapsackDp(n,c,w,v,path);for (int i = 0; i <=n ; ++i) {for (int j = 0; j <= c ; ++j) {printf("%d    ",dp[i][j]);}printf("\n");}for (int i = 0; i <=n ; ++i) {for (int j = 0; j <= c ; ++j) {printf("%d    ",path[i][j]);}printf("\n");}printf("================output==================\n");while ( n >0 && c >0 ){if(path[n][c]==1){c = c-w[n-1];printf("the %d put the package!\n",n);}n--;}
}

result

2.最长公共子序列

先看一张动态图
lcs
代码实现也很简单了

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

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

相关文章

电脑版剪映怎么倒放?

1.打开一个素材 2.添加到时间轨道 3.右击轨道素材 弹出的选项钟选择&#xff0c;基础编辑》倒放&#xff01;

计算机网络分类

按照覆盖范围分类 &#xff08;1&#xff09;个域网&#xff1a;通常覆盖范围在1&#xff5e;10m。 &#xff08;2&#xff09;局域网&#xff1a;通常覆盖范围在10m&#xff5e;1km。 &#xff08;3&#xff09;城域网&#xff1a;覆盖范围通常在5&#xff5e;50 km 。 &…

蓝桥杯 题库 简单 每日十题 day5

01 字符计数 字符计数 题目描述 给定一个单词&#xff0c;请计算这个单词中有多少个元音字母&#xff0c;多少个辅音字母。 元音字母包括a,e&#xff0c;i,o&#xff0c;u&#xff0c;共五个&#xff0c;其他均为辅音字母。 输入描述 输入格式&#xff1a; 输入一行&#xff0…

Xcode15+iOS17适配以及遇到的问题

今天更新了 Xcode15&#xff0c;遇到了一些问题&#xff0c;做下记录希望大家少走点坑。 1.iOS17 SDK 安装失败 Xcode更新完成后&#xff0c;打开项目一直显示 no fund iOS17 sdk&#xff0c;根据项目不同提示可能有区别&#xff0c;根据提示下载后提示安装失败&#xff0c;…

针对 SAP 的增强现实技术

增强现实技术是对现实世界的一种交互式模拟。这种功能受到各种企业和制造商的欢迎&#xff0c;因为它可以减少生产停机时间、快速发现问题并维护流程&#xff0c;从而提高运营效率。许多安卓应用都在探索增强现实技术。 使用增强现实技术&#xff08;AR&#xff09;的Liquid U…

svn(乌龟svn)和SVN-VS2022插件(visualsvn) 下载

下载地址: https://www.visualsvn.com/visualsvn/download/

备受以太坊基金会青睐的 Hexlink,构建亿级用户涌入 Web3的入口

早在 2021 年 9 月&#xff0c;以太坊创始人 Vitalik Buterin 就曾提出了 EIP-4337&#xff08;账户抽象&#xff09;提案&#xff0c;并在去年 10 月对该提案进一步更新&#xff0c;引发行业的进一步关注。在今年 3 月&#xff0c;EIP-4337 提案正式通过审计&#xff0c;并成为…

centos 7.9系统安装向日葵

1.下载地址 向日葵远程控制app官方下载 - 贝锐向日葵官网 2.下载依赖 yum install -y libappindicator-gtk3 安装好依赖之后&#xff0c;然后再安装向日葵软件 3.安装软件 sudo rpm -ivh 文件名.rpm 4.安装成功之后的位置

VR赋能红色教育,让爱国主义精神永放光彩

昨天的918防空警报长鸣&#xff0c;人们默哀&#xff0c;可见爱国主义精神长存。为了贯彻落实“把红色资源利用好、红色传统发扬好、红色基因传承好”的指示精神&#xff0c;许多红色景点开始引入VR全景展示技术&#xff0c;为游客提供全方位720度无死角的景区展示体验。 VR全…

MySQL详解六:备份与恢复

文章目录 1. 数据库备份的分类1.1 从物理和逻辑上分类1.1.1 物理备份1.1.2 逻辑备份 1.2 从数据库的备份策略角度上分类1.2.1 完全备份1.2.2 差异备份1.2.3 增量备份 1.3 常见的备份方法 2. MySQL完全备份2.1 完全备份简介2.2 优点与缺点2.3 实现物理冷备份与恢复2.3.1 实现流程…

海外代理IP是什么?如何使用?

一、海外代理IP是什么&#xff1f; 首先&#xff0c;代理服务器是在用户和互联网之间提供网关的系统或路由器。它是一个服务器&#xff0c;被称为“中介”&#xff0c;因为它位于最终用户和他们在线访问的网页之间。 海外IP代理是就是指从海外地区获取的IP地址&#xff0c;用…

redis实战-实现笔记点赞和点赞排行榜

发布探店笔记 探店笔记类似点评网站的评价&#xff0c;往往是图文结合。对应的表有两个&#xff1a; tb_blog&#xff1a;探店笔记表&#xff0c;包含笔记中的标题、文字、图片等 tb_blog_comments&#xff1a;其他用户对探店笔记的评价 保存笔记service层 Overridepublic Re…

Mybatis学习笔记9 动态SQL

Mybatis学习笔记8 查询返回专题_biubiubiu0706的博客-CSDN博客 动态SQL的业务场景&#xff1a; 例如 批量删除 get请求 uri?id18&id19&id20 或者post id18&id19&id20 String[] idsrequest.getParameterValues("id") 那么这句SQL是需要动态的 还…

AJAX学习

文章目录 创建 XMLHttpRequest 对象向服务器发送请求XMLHttpRequest.open()XMLHttpRequest.send()GET或POST 服务器响应XMLHttpRequest 的属性XMLHttpRequest.readyStateXMLHttpRequest.onreadystatechangeXMLHttpRequest.responseXMLHttpRequest.responseTypeXMLHttpRequest.r…

软件工程之总体设计

总体设计是软件工程中的一个重要阶段&#xff0c;它关注整个系统的结构和组织&#xff0c;旨在将系统需求转化为可执行的软件解决方案。总体设计决定了系统的架构、模块划分、功能组织以及数据流和控制流等关键方面。 可行性研究 具体方面&#xff1a;经济可行性、技术可行性…

PY32F003F18之DMA串口

PY32F003F18使用DMA串口&#xff0c;官方程序省FLASH&#xff0c;但不省内存。单片机内存够大&#xff0c;节省没意义&#xff0c;故做了修改&#xff0c;少用HAL库中的发送和接收&#xff0c;从里面抠出有用的部分&#xff0c;修修改改就可以了。 一、DMA串口初始化流程&…

Vue页面快速使用阿里巴巴矢量图标库

前面我已经写个一篇文章 阿里巴巴矢量图标如何使用_turbo夏日漱石的博客-CSDN博客 这篇文章非常详细地讲解了在html页面中如何使用阿里巴巴矢量图标库 下面我们讲解在vue页面中引入阿里巴巴矢量图标库icon的几种方法 目录 一、引入在线链接 1、 第九步链接引入在vue中应该是在…

安卓备份基带分区 备份字库 步骤解析 以免误檫除分区或者“格机” 后悔莫及

玩机搞机---安卓机型mtk和高通芯片查看分区 导出分区 备份分区的一些工具分析 修复基带 改串码 基带qcn 改相关参数 格机危害 手机基带的重要性前面几期博文我都有相关的说明。他区别于别的分区。而且目前手机的安全性越来越高。基带分区基本都是专机专用。而不像早期机型一…

【AI语言大模型】文心一言功能使用介绍

一、前言 文心一言是一个知识增强的大语言模型&#xff0c;基于飞桨深度学习平台和文心知识增强大模型&#xff0c;持续从海量数据和大规模知识中融合学习具备知识增强、检索增强和对话增强的技术特色。 最近收到百度旗下产品【文心一言】的产品&#xff0c;抱着试一试的心态体…

java服务内存说明及配置详解

java进程内存 JVM内存分布图: 【java进程内存】【堆外内存】 【jvm堆内存】 【堆外内存】 【Metaspace】 【Direct Memory】【JNI Memory】【code_cache】 … 堆外内存泄漏的排查在于【本地内存&#xff08;Native Memory&#xff09;】【Direct Memory】【JNI Memory】 一般…