动态规划算法（3）--0-1背包、石子合并、数字三角形

目录

一、0-1背包

1、概述

2、暴力枚举法

3、动态规划

二、石子合并问题

1、概述

2、动态规划

3、环形石子怎么办？

三、数字三角形问题

1、概述

2、递归

3、线性规划

 四、租用游艇问题 

一、0-1背包

1、概述

        0-1背包：给定多种物品和一个固定重量W的背包，每种物品有一个固定的重量w_i，价值v_i，现在要将物品装入背包，每种物品至多装入一个，使总重量不超过W，且总价值最大。

        约束条件和优化目标如下：

2、暴力枚举法

        暴力枚举法也是使用递归的方式，假设对前i个物品分析，总重量为c，当前总价值为P。那么存在递归条件：\begin{matrix} \quad \qquad p1=knapsack(i-1,c-w_i)\\ \quad p2=knapsack(i-1,c) \\ P=max(p1+v_i,p2) \end{matrix}

        另外当重量小于0时，总价值为-∞（代码中可以用-999替代），物品个数小于等于0，总价值为0。

        暴力枚举法依赖递归方式，没有减少子问题个数，所以根据递归树计算，复杂度为O(2^n)。

        伪代码如下：

        代码实例： 

   //暴力枚举public static int violate_knapsack(int weight,int i,int weights[],int values[]){if (weight<0){return -9999; }if (i<=0)  {    return 0;}int p1=violate_knapsack(weight-weights[i],i-1,weights,values);   //选中i物品int p2=violate_knapsack(weight,i-1,weights,values);              //不选i物品int p=p1+values[i]>p2?p1+values[i]:p2;   return p;}

3、动态规划

        动态规划方法通过建立备忘录的方式，前i个物品，总重量为j的时刻永远依赖于前面的子结构。M数组为加入前i个物品后，总重量为j时的总价值，Rec数组表示是否有物品添加，若添加则为1，不添加则为0。

        原理：

参数：count代表总类别个数，weight代表背包重量，weights为物品重量，values为物品价值，name为物品名称。

（1）首先，M数组0行0列均为初值0，注意：行为重量，列为种类个数。

（2）按每行逐个值来填写M和Rec。如：前i个物品，总重量为j的情况下，即求M[i][j]时，如果该物品重量小于背包重量且在前i-1个物品，总重量为（j-当前物品重量）时的总重量+当前物品价值的总价值，大于前i-1个物品，总重量为j时的总价值时M填写较大的总价值，Rec=1。条件写为：weights[i-1]\leqslant j,values[i-1]+M[i-1][j-weights[i]]>M[i-1][j]

（3）由于调用j-当前物品重量时有可能为负数，所以保证最小值为0，设为minor。

（4）如果不满足（2）条件，则M[i][j]填上一行同列的M[i-1][j]值，即不选这个物品（索引为i-1）的总价值。Rec为0。

（5）最优解追寻：Rec数组倒序查找i取最大值，逐次减1，判断条件如果Rec数组为1，则从总重量weight中减少weights[i-1]，输出name[i-1]物品，直到i取1。

//0-1背包问题
import java.util.ArrayList;
public class backage {public static void main(String []args){int values[]={24,2,9,10,9};int weights[]={10,3,4,5,4};int count=5;int weight=13;int M[][]=new int [count+1][weight+1];int Rec[][]=new int [count+1][weight+1];String name[]={"beer","cocacola","cookie","bread","milk"};//暴力求解System.out.println(violate_knapsack(weight,count-1,weights,values));  //建立M数组，Rec数组 knapsack(count,weight,M,Rec,weights,values);//M数组for(int i=0;i<count+1;i++){for(int j=0;j<weight+1;j++){System.out.print(M[i][j]+"\t");}System.out.println("");}//Rec数组for(int i=0;i<count+1;i++){for(int j=0;j<weight+1;j++){System.out.print(Rec[i][j]+"\t");}System.out.println("");}//输出最优解Print(count,weight,Rec,name,weights);} //动态规划public static void knapsack(int count,int weight,int M[][],int Rec[][],int weights[],int values[]){for(int i=0;i<count+1;i++)         //0行0列没有值参与M[i][0]=0;for(int j=0;j<weight+1;j++)M[0][j]=0;for(int i=1;i<count+1;i++)         //第一行的表示加入第一个物品，但是第一个物品在索引0处{for(int j=1;j<weight+1;j++){int minor;                 //minor的设计是防止j-weights出现小于0，有可能背包重量小于上一行物品的重量，从而小于背包质量，小于背包质量默认为0if(j-weights[i-1]<0)minor=0;elseminor=j-weights[i-1];if((weights[i-1]<=j) & (values[i-1]+M[i-1][minor]>M[i-1][j]))    //如果可以替换,M替换为新值，Rec更新为1{M[i][j]=values[i-1]+M[i-1][minor];Rec[i][j]=1;}else{M[i][j]=M[i-1][j];                                           //不能修改时，M用上一行同列值替换，Rec更新为0Rec[i][j]=0;}}}}//输出最优解public static void Print(int count,int weight,int Rec[][],String name[],int weights[]){for(int i=count;i>0;i--){if(Rec[i][weight]==1){System.out.println(name[i-1]);weight=weight-weights[i-1];}}}

M数组和Rec数组的写法：

二、石子合并问题

1、概述

        现在有n堆石子排成一排，要求将石子有次序地合并成一堆，规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分，设计一个算法将n堆石子合并成一堆的最小得分和最大得分。

        类比矩阵连乘问题求解，利用动态规划，设计m和s数组，最大值为m[1][n]。

2、动态规划

        动态规划转移方程（最小值）：

        m[i][j]=\begin{Bmatrix} 0 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad i=j\\ min(m[i][k]+m[k+1][j]+sum(i,j)) \quad i<j \end{Bmatrix}

        动态规划转移方程（最大值）：

 m[i][j]=\begin{Bmatrix} 0 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad i=j\\ max(m[i][k]+m[k+1][j]+sum(i,j)) \quad i<j \end{Bmatrix}

3、环形石子怎么办？

        如果题目要求石子堆围成一圈，其他要求不变，我们可以考虑将数组变为一个重复数组，由环形变为线性。如{1,2,3}则变为{1,2,3,1,2,3}，n=2*n，然后考虑(j-i)>=arr_length时才满足原来的最多三个石子堆合并的问题。

        动态规划转移方程相同，只是多了一个退出循环的条件，同样的生成m数组，假设石子堆为{4,4,5,9}，当前生成最小值m数组应该为下图示例：

        可以看到原先的m[1][n]为最小值，现在应该讨论min(m[i][n+i-1]) \quad 1\leqslant i\leqslant n，也就是四个数的最小值。

        代码示例：

//石子合并问题
public class stonemerge {public static void main(String[] args){int arr[]={4,4,5,9};int n=arr.length;int m[][]=new int[n+1][n+1]; int m_[][]=new int[n*2+1][n*2+1];int s[][]=new int[n+1][n+1]; minserge(arr,m_);System.out.println(trackmin(arr, m_));maxserge(arr, m_);System.out.println(trackmax(arr,m_));}//最小合并m数组 public static void minserge(int arr_[],int m[][]){int n=arr_.length*2;int arr[]=new int[n];add_arr(arr,arr_);for(int i=1;i<n;i++)m[i][i]=0;for (int r = 2; r <=n; r++) {for (int i = 1; i <= n - r + 1; i++) {               int j = i + r - 1;if((j-i)>=arr_.length)break;                m[i][j] = m[i + 1][j] + sum(i,j,arr);				             for (int k = i + 1; k < j; k++){int t = m[i][k] + m[k + 1][j] + sum(i,j,arr);if (t < m[i][j]) m[i][j] = t;}}}}//最大合并m数组public static void maxserge(int arr_[],int m[][]){int n=arr_.length*2;int arr[]=new int[n];add_arr(arr,arr_);for(int i=1;i<n;i++)m[i][i]=0;for (int r = 2; r <=n; r++) {for (int i = 1; i <= n - r + 1; i++) {               int j = i + r - 1;if((j-i)>=arr_.length)break;                m[i][j] = m[i + 1][j] + sum(i,j,arr);				             for (int k = i + 1; k < j; k++){int t = m[i][k] + m[k + 1][j] + sum(i,j,arr);if (t > m[i][j]) m[i][j] = t;}}}}//合并代价public static int sum(int i,int j, int arr[]){int tot=0;for(int m=i-1;m<=j-1;m++)tot+=arr[m];return tot;}//环形转线性数组生成public static void add_arr(int arr[],int arr_[]){for(int i=0;i<arr.length;i++){if(i<arr_.length)arr[i]=arr_[i];elsearr[i]=arr_[i-arr_.length];}}//最小值public static int trackmin(int arr[],int m[][]){int n=arr.length;int min=m[1][n];for(int i=2;i<=n;i++){if(m[i][n+i-1]<min)min=m[i][n+i-1];}return min;}//最大值public static int trackmax(int arr[],int m[][]){int n=arr.length;int max=m[1][n];for(int i=2;i<=n;i++){if(m[i][n+i-1]>max)max=m[i][n+i-1];}return max;}
}

三、数字三角形问题

1、概述

        给定一个由n行数字组成的数字三角形，设计算法，计算从三角形的顶至底的一条路径，每次必须下降一层，使该路径经过数字总和最大，如下图路线7-3-8-7-5，总和30。

2、递归

递归条件：

nums[x][y]+=max(trest(x+1,y),test(x+1,y+1)) \ x\neq n-1

               当x==n-1时为最底层数字，返回该数字。

//递归方法
public static int test(int x,int y,int nums[][]) {int n=nums.length;if(x == n-1) {return nums[x][y];}return (nums[x][y] + (test(x+1,y,nums) >= test(x+1,y+1,nums) ? test(x+1,y,nums) : test(x+1,y+1,nums)));}

3、线性规划

        状态转移方程与递归条件一样，只不过从倒数第二层向上叠加（参数i），每层的值改变为当前层到底层的最大值，变量k遍历某一层的每个数字，计算到底层的最大值并保存。

//动态规划
public static int max(int nums[][])
{for(int i=nums.length-2;i>=0;i--){int j=nums[i].length;for(int k=0;k<j;k++){nums[i][k]+=(nums[i+1][k]>=nums[i+1][k+1]?nums[i+1][k]:nums[i+1][k+1]);}}return nums[0][0];
}

 四、租用游艇问题

        游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇，游艇出租站i到游艇出租站j之间的租金为r（i，j）（1<=i<j<=n）,设计算法，计算出游艇出租站1到游艇出租站n的最少租金。

        输入的数字，第一行代表1到2的距离和1到3的距离，第二行代表2到3的距离。一般输入的二维数组都是起始从1开始，以主对角线分布的，这一点可以参见三角形剖分问题。

        租用游艇问题其实本质上也是一个矩阵相乘的问题，所以可以共用矩阵相乘的函数嵌套部分，记住（i，j）的执行顺序就是dp数组的计算顺序。

        dp数组原理：首先dp数组等于cost数组值，若i和j之间存在一个整数，则定义k，使得dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]) \quad 1\leqslant i< k<j\leqslant n

        代码示例：

//租用游艇问题
import java.util.Scanner;
public class rentyacht {public static void main(String [] args){int n=new Scanner(System.in).nextInt();int [][]cost=new int[200][200];int [][]dp=new int[200][200];for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){cost[i][j]=new Scanner(System.in).nextInt();}}System.out.println(rentmin(cost,dp,n));} public static int rentmin(int[][] cost, int [][]dp,int n) {for(int r=2;r<=n;r++){for(int i=1;i<=n-r+1;i++){int j=i+r-1;dp[i][j]=cost[i][j];for(int k=i+1;k<j;k++){dp[i][j]=Math.min(cost[i][j],cost[i][k]+cost[k][j]);}}}return dp[1][n];}
}

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

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

相关文章

采用医疗AI、自然语言处理技术的java智能导诊导医系统源码

采用医疗AI、自然语言处理技术的java智能导诊导医系统源码

一套java智能导诊导医系统源码&#xff08;演示自主版权商业项目应用&#xff09; 随着人工智能技术的快速发展&#xff0c;语音识别与自然语言理解技术的成熟应用&#xff0c;基于人工智能的智能导诊导医逐渐出现在患者的生活视角中&#xff0c;智能导诊系统应用到医院就医场景…
阅读更多...
Kotlin Compose Multiplatform 跨平台开发实践之加入 iOS 支持

Kotlin Compose Multiplatform 跨平台开发实践之加入 iOS 支持

前言 几个月前 Compose Multiplatform 的 iOS 支持就宣布进入了 Alpha 阶段&#xff0c;这意味着它已经具备了一定的可用性。 在它发布 Alpha 的时候&#xff0c;我就第一时间尝鲜&#xff0c;但是只是浅尝辄止&#xff0c;没有做过多的探索&#xff0c;最近恰好有点时间&…
阅读更多...
计算机网络-计算机网络体系结构-网络层

计算机网络-计算机网络体系结构-网络层

目录 一、IPV4 IP数据报格式 *IP 数据报分片 *IPV4地址 分类 网络地址转换(NAT) 二、子网划分与子网掩码 *CIDR *超网 协议 ARP协议 DHCP协议 ICMP协议 三、IPV6 格式 IPV4和IPV6区别 地址表示形式 四、路由选择协议 RIP(路由信息协议) OPSF(开发最短路径优…
阅读更多...
SpringBoot整合Caffeine实现缓存

SpringBoot整合Caffeine实现缓存

Caffeine Caffeine是一种基于Java的高性能缓存库&#xff0c;它提供了可配置、快速、灵活的缓存实现。Caffeine具有以下特点&#xff1a; 高性能&#xff1a;Caffeine使用了一些优化技术&#xff0c;如基于链表的并发哈希表和无锁算法&#xff0c;以提供卓越的读写性能。容量…
阅读更多...
nodejs+vue 学生宿舍管理系统设计与实现

nodejs+vue 学生宿舍管理系统设计与实现

可将教师信息、宿管信息、学生信息、楼栋信息等输入到系统中。只有管理员才能录入相关的资料&#xff0c;按照提示&#xff0c;输入相应的资料&#xff0c;而“导入”则可以通过上传档案&#xff0c;导入成功后&#xff0c;相应的寝室就会相应的减少。在录入大楼的时候&#xf…
阅读更多...
Filebeat+Kafka+ELK日志分析架构

Filebeat+Kafka+ELK日志分析架构

目录 一、zookeeper&#xff1a; 1. zookeeper 定义&#xff1a; 2. Zookeeper 工作机制: 3. Zookeeper 特点: 4. Zookeeper 数据结构: 5. Zookeeper 应用场景: 5.1 统一命名服务: 5.2 统一配置管理: 5.3 统一集群管理: 5.4 服务器动态上下线: 5.5 软负载均衡: 6. Zookeeper 选…
阅读更多...
MAYA教程之建模基础命令介绍

MAYA教程之建模基础命令介绍

基础命令 视图相关操作 旋转视图 : ALT 鼠标左键平移视图 : ALT 鼠标中键缩放视图 : 滚动鼠标滚轮 或者 ALT 鼠标右键切换视图 : 空格键回到模型 : F 视图状态 选择状态 : Q移动状态 : W旋转状态 : E缩放状态 : R 视图显示 正常显示 : 1正常圆滑同时显示 : 2圆滑显示 …
阅读更多...
C#中List、Dictionary、HashSet用法以及区别

C#中List、Dictionary、HashSet用法以及区别

前言 在C#编程中&#xff0c;List、Dictionary和HashSet是常用的集合类型,它们都有自己的特点和适用场景。本篇博客将介绍它们的用法、区别及常见操作。深入了解这些集合类型&#xff0c;能够帮助我们更好地组织和处理数据。 1. List: List是一个有序可重复集合&#xff0c;可…
阅读更多...
Hadoop3教程（二十二）：Yarn的基础架构与工作流程

Hadoop3教程（二十二）：Yarn的基础架构与工作流程

文章目录 &#xff08;126&#xff09;基础架构&#xff08;127&#xff09;YARN的工作机制&#xff08;128&#xff09;作业全流程参考文献 &#xff08;126&#xff09;基础架构 之前基本介绍完了Hadoop的几个核心组件&#xff0c;接下来可以思考下&#xff0c;在MR程序运行…
阅读更多...
Camera BSP之GPIO/I2C/PMIC简介

Camera BSP之GPIO/I2C/PMIC简介

和你一起终身学习&#xff0c;这里是程序员Android 经典好文推荐&#xff0c;通过阅读本文&#xff0c;您将收获以下知识点: 一、GPIO介绍二、IC 总线概括三、PMIC 概括四、思考 一、GPIO介绍 GPIO&#xff1a;General Purpose Input Output &#xff08;通用输入/输出&#xf…
阅读更多...
【iOS】JSONModel的基本使用

【iOS】JSONModel的基本使用

文章目录 前言一、导入JSONModel二、JSONModel的基本使用1.基本用法2.模型集合3.模型导出为NSDictionary或JSON4.设置所有属性可选&#xff08;所有属性值可以为空&#xff09;5.下划线(蛇式)转驼峰命名法 前言 JSONModel 是一个用于 Objective-C 的开源库&#xff0c;它用于简…
阅读更多...
（三十四）大数据实战——scala运行环境安装配置及IDEA开发工具集成

（三十四）大数据实战——scala运行环境安装配置及IDEA开发工具集成

前言 本节内容我们主要介绍一下scala运行环境的安装配置以及在idea开发工具中集成scala插件&#xff0c;便于scala项目的开发。 在开始scala安装配置之前&#xff0c;我们要先安装好jvm运行环境&#xff0c;scala运行于Java虚拟机&#xff08;JVM&#xff09;上&#xff0c;并…
阅读更多...
TCP/IP五元组

TCP/IP五元组

什么是五元组规则&#xff1f; 五元组是通信术语&#xff0c;英文名称为five-tuple,或5-tuple&#xff0c;五元组包括源IP地址(source IP)、源端口(source port)、目的IP地址(destination IP)、目的端口(destination port) 和 传输层协议(the layer 4 protocol)的五个量集合。…
阅读更多...
【API篇】四、Flink物理分区算子API

【API篇】四、Flink物理分区算子API

文章目录 1、 分区算子&#xff1a;随机分区2、分区算子&#xff1a;轮询分区3、分区算子&#xff1a;重缩放分区4、分区算子&#xff1a;广播5、分区算子&#xff1a;全局分区6、自定义分区 重分区&#xff0c;即数据"洗牌"&#xff0c;将数据分配到下游算子的并行子…
阅读更多...
互联网Java工程师面试题·Java 总结篇·第八弹

互联网Java工程师面试题·Java 总结篇·第八弹

目录 72、用 Java 的套接字编程实现一个多线程的回显&#xff08;echo&#xff09;服务器。 73、XML 文档定义有几种形式&#xff1f;它们之间有何本质区别&#xff1f;解析XML 文档有哪几种方式&#xff1f; 74、你在项目中哪些地方用到了 XML&#xff1f; 72、用 Java 的套…
阅读更多...
如何注册微信小程序

如何注册微信小程序

如何注册微信小程序 前言 因为最近沉迷和朋友们一起下班去打麻将&#xff0c;他们推荐了一个计分的小程序&#xff0c;就不需要每局都转账或者用扑克牌记录了&#xff0c;但是这个小程序不仅打开有广告&#xff0c;各个页面都植入了广告&#xff0c;用起来十分不适。 于是我…
阅读更多...
Freemarker快速入门（SpringBoot版）

Freemarker快速入门（SpringBoot版）

文章目录 Freemarker快速入门1、Freemarker概述2、Freemarker初体验3、数据类型3.0 常见操作符3.1 数值类型3.2 字符串类型3.3 布尔类型3.4 日期类型3.5 序列类型3.6 哈希类型 4、运算符4.1 算术运算符4.2 逻辑运算符4.3 比较运算符4.4 空值运算符 5、常用指令5.1 assign 自定义…
阅读更多...
热门影视APP系统源码 可二开 后端+app+搭建教程

热门影视APP系统源码 可二开 后端+app+搭建教程

影视APP源码绿豆二开版 后端app搭建教程都在压缩包里&#xff0c;搭建步骤和绿豆一样 安装宝塔 yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh 安装环境 Nginx 1.20.2 MySQL5.6-5.7 php7.0-7.…
阅读更多...
使用 VS Code 作为 VC++ 6.0 的编辑器

使用 VS Code 作为 VC++ 6.0 的编辑器

使用 VS Code 作为 VC 6.0 的编辑器 由于一些众所周知的原因&#xff0c;我们不得不使用经典&#xff08;过时&#xff09;的比我们年龄还大的已有 25 年历史的 VC 6.0 来学习 C 语言。而对于现在来说&#xff0c;这个经典的 IDE 过于简陋&#xff0c;并且早已不兼容新的操作系…
阅读更多...
tomcat、nginx实现四层转发+七层代理+动静分离实验

tomcat、nginx实现四层转发+七层代理+动静分离实验

实验环境&#xff1a; nginx1——20.0.0.11——客户端 静态页面&#xff1a; nginx2——20.0.0.21——代理服务器1 nginx3——20.0.0.31——代理服务器2 动态页面&#xff1a; tomcat1——20.0.0.12——后端服务器1 tomcat2——20.0.0.22——后端服务器2 实验步骤&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023