当前位置: 首页 > news >正文

Javascript动态规划算法

JavaScript中的动态规划(Dynamic Programming,简称DP)是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它主要致力于将“合适”的问题拆分成更小的子目标,并通过建立状态转移方程、缓存并复用以往结果以及按顺序从小往大算这三个步骤来解决问题。以下是对js动态规划算法的详细解析:

一、动态规划的基本概念

  1. 状态转移方程:动态规划的核心是找到一个能够描述问题状态转移的数学方程,即状态转移方程。这个方程描述了如何从较小的子问题的解推导出较大问题的解。
  2. 缓存并复用以往结果:为了避免重复计算,动态规划会将已经计算过的子问题的解存储起来,以便在后续的计算中直接引用。这通常通过一个数组或对象来实现,称为DP表。
  3. 按顺序从小往大算:动态规划通常按照某种顺序(如从小到大的子问题规模)来计算子问题的解,并最终得到原问题的解。

二、动态规划的应用示例

  1. 斐波那契数列

斐波那契数列是一个经典的动态规划问题。数列中的每个数字是前两个数字之和,通常以0和1开始。使用动态规划可以避免直接递归方法中的大量重复计算。

JavaScript代码示例:

function fibonacci(n, memo = []) {  // 初始化记忆数组  memo[0] = 0;  memo[1] = 1;  // 如果已经计算过该值,直接从记忆数组返回  if (memo[n] !== undefined) {  return memo[n];  }  // 递归计算斐波那契数,同时利用记忆化存储结果  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);  return memo[n];  
}  // 示例  
console.log(fibonacci(10)); // 输出第10个斐波那契数

在这个例子中,memo数组用于存储已经计算过的斐波那契数,从而避免了重复计算。

  1. 01背包问题

01背包问题是另一个经典的动态规划问题。它描述了一个背包可以装载的最大重量为W,有N件物品,每件物品有一个重量和一个价值。要求选择若干件物品装入背包,使得背包中物品的总价值最大,同时不超过背包的最大重量。

JavaScript代码示例:

const w = [1, 4, 3]; // 物品重量  
const value = [1500, 3000, 2000]; // 物品的价值  
const m = 4; // 背包容量  
const n = 3; // 物品的个数  // 二维数组v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值  
let v = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));  // 遍历物品和背包容量  
for (let i = 1; i <= n; i++) {  for (let j = 1; j <= m; j++) {  if (w[i - 1] > j) {  v[i][j] = v[i - 1][j];  } else {  v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - w[i - 1]]);  }  }  
}  console.log(v[n][m]); // 输出最大价值

核心:Math.max(v[i-1][j],  value[i - 1] + v[i - 1][j - w[i - 1]])

在这个例子中,二维数组v用于存储子问题的解。通过遍历物品和背包容量,可以逐步计算出在前i个物品中能够装入容量为j的背包中的最大价值。 

 

放了那些商品?【待思考】

function knapsack(weights, values, maxWeight) {  const n = weights.length;  // 创建一个二维数组dp,dp[i][w]表示前i个物品在重量不超过w的情况下的最大价值  const dp = Array.from({ length: n + 1 }, () => Array(maxWeight + 1).fill(0));  // 记录选择的物品  const selectedItems = Array.from({ length: n + 1 }, () => Array(maxWeight + 1).fill(false));  // 动态规划填表  for (let i = 1; i <= n; i++) {  for (let w = 0; w <= maxWeight; w++) {  if (weights[i - 1] <= w) {  if (dp[i - 1][w] + values[i - 1] > dp[i - 1][w]) {  dp[i][w] = dp[i - 1][w] + values[i - 1];  selectedItems[i][w] = true;  } else {  dp[i][w] = dp[i - 1][w];  }  } else {  dp[i][w] = dp[i - 1][w];  }  }  }  // 最大价值  const maxValue = dp[n][maxWeight];  // 追溯选择的物品  const selected = [];  let currentWeight = maxWeight;  for (let i = n; i > 0; i--) {  if (selectedItems[i][currentWeight] && dp[i][currentWeight] !== dp[i - 1][currentWeight]) {  selected.push(i - 1); // 物品索引从0开始,需要减1  currentWeight -= weights[i - 1];  }  }  return {  maxValue: maxValue,  selectedItems: selected  };  
}  // 示例  
const weights = [2, 3, 4, 5];  
const values = [3, 4, 5, 6];  
const maxWeight = 5;  const result = knapsack(weights, values, maxWeight);  
console.log(`最大价值: ${result.maxValue}`);  
console.log(`选择的物品索引: ${result.selectedItems}`);  
console.log(`选择的物品: ${result.selectedItems.map(index => `物品${index + 1}`).join(', ')}`);

三、动态规划的优点和局限性

  1. 优点

    • 能够高效地解决具有重叠子问题的问题。
    • 通过缓存和复用以往结果,避免了大量的重复计算。
  2. 局限性

    • 只适用于具有最优子结构和重叠子问题的问题。
    • 对于某些问题,可能需要大量的空间来存储子问题的解(即DP表)。

四、总结

JavaScript中的动态规划是一种强大的算法设计范式,适用于解决具有重叠子问题的问题。通过建立状态转移方程、缓存并复用以往结果以及按顺序从小往大算这三个步骤,可以高效地求解复杂问题。然而,动态规划也有一定的局限性,只适用于具有最优子结构和重叠子问题的问题。在实际应用中,需要根据问题的特点选择合适的算法设计范式来求解。

相关文章:

Javascript动态规划算法

JavaScript中的动态规划&#xff08;Dynamic Programming&#xff0c;简称DP&#xff09;是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它主要致力于将“合适”的问题拆分成更小的子目标&#xff0c;并通过建立状态转移方程、缓存并复用以往结果以及按…...

Java 循环里怎么删除元素才安全

首先 在 Java 中&#xff0c;当你在循环中遍历集合时&#xff0c;直接删除元素可能会引发 ConcurrentModificationException。为了安全地删除元素&#xff0c;推荐使用 Iterator 来进行删除操作。 以下是使用 Iterator 删除元素的常见模式&#xff1a; import java.util.Arr…...

LabVIEW晶体振荡器自动化测试系统

基于LabVIEW平台的晶体振荡器自动化测试系统解决了传统手工测试晶体振荡器繁琐且易出错的问题。该系统通过高度自动化的测试流程&#xff0c;提高了测试效率和精度&#xff0c;实现了数据的自动采集与处理&#xff0c;适用于电子、通信等领域的晶振测试需求。 项目背景与意义 …...

3.6.xx版本SpringBoot创建基于Swagger接口文档

介绍 基于Swagger构建的JavaAPI文档工具&#xff0c;实现后端功能的测试&#xff0c;并撰写API接口文档。 方法 pom.xml中引入依赖,要注意的是&#xff0c;本依赖使用的SpringBoot版本为3.6.xx <!--Knife4j--><dependency><groupId>com.github.xiaoymin<…...

Oracle 12201非PDBS模式单机部署(静默安装)

一、创建Oracle数据库的用户 groupadd oinstall groupadd dba groupadd asmadmin groupadd asmdba useradd -g oinstall -G dba,asmdba oracle -d /home/oracle passwd oracle二、配置Linux 服务器参数 cat /home/oracle/.bash_profile export ORACLE_HOSTNAMEH_orcle01 expo…...

Python 源码编译安装详解:跨平台指南及完整步骤解析

Python 源码编译安装详解&#xff1a;跨平台指南及完整步骤解析 文章目录 Python 源码编译安装详解&#xff1a;跨平台指南及完整步骤解析一 准备工作1&#xff09;Ubuntu/Debian2&#xff09;CentOS/RHEL3&#xff09;macOS 二 下载 Python 源码三 编译与安装1&#xff09;解压…...

MQTT vs HTTP:谁更适合物联网?

前言 随着物联网&#xff08;IoT&#xff09;技术的飞速发展中&#xff0c;其应用规模和使用场景正在持续扩大&#xff0c;但它关键的流程仍然是围绕数据传输来进行的&#xff0c;因此设备通信协议选择至关重要。 作为两种主要的通信协议&#xff0c;MQTT 协议和 HTTP 协议各…...

小北的技术博客:探索华为昇腾CANN训练营与AI技术创新——Ascend C算子开发能力认证考试(初级)

前言 哈喽哈喽友友们,这里是zyll~(小北)智慧龙阁的创始人及核心技术开发者。在技术的广阔天地里,我专注于大数据与全栈开发,并致力于成为这一领域的新锐力量。通过智慧龙阁这个平台,我期望能与大家分享我的技术心得,共同探索技术的无限可能。 Ascend C编程:小北的技术…...

鸿蒙next开发者第一课02.DevEcoStudio的使用-习题

【习题】DevEco Studio的使用 通过/及格分80/ 满分100 判断题 1. 如果代码中涉及到一些网络、数据库、传感器等功能的开发&#xff0c;均可使用预览器进行预览。F 正确(True)错误(False) 预览器不能进行传感器等特殊功能的开发,需要使用真机开发 2. module.json5文件中的…...

【vue】监听table水平滚动条切换tab后还原位置

有个需求就是切换tab后&#xff0c;原先的table水平滚动条要还原位置&#xff08;如下图&#xff09;&#xff0c;先说下思路&#xff0c;大致就是 切出页面时 把滚动距离保存到Storage 中&#xff0c;切回来时在恢复 直接上代码 首先table ref指定一下ref"jtable" …...

C#使用PdfSharp生成PDF文件实例详解

许多项目开发中需要生成PDF, 常规办法使用官方提供的Microsoft.Office.Interop.Worddll插件,但是这种方法需要完全安装OFFICE,另外版本不一致还会出现很多错误。一般不推荐使用。 下面介绍几种巧妙的用法,定能事半功倍。 本文使用PDFsharp完成功能。 PDFsharp一款开源的…...

【软件系统架构设计师-案例-1】架构风格

1. 请用200字以内说明系统可靠性的定义及包含的4个子特性&#xff0c;并简要指出提高系统可靠性一般采用哪些技术&#xff1f; &#xff08;1&#xff09;可靠性定义&#xff1a;系统在规定的时间或环境条件下&#xff0c;完成规定功能的能力&#xff0c;就是系统无故障运行的…...

神经网络整体架构

文章目录 1.输入层Input2.卷积层Conv3.激活函数层(一)Sigmoid 函数(二)Tanh 函数(三)修正线性单元ReLU(四)Leaky ReLU函数(带泄露的Relu)(五)参数化ReLU 4.池化层POOL5.全连接层FC6.输出层Output 用全连接神经网络处理大尺寸图像具有三个明显的缺点&#xff1a; ①将图像展开为…...

山西农业大学20241010

02-JAVASCRIPT 一.JS基础语法1. 数据类型转换1.1 隐式转换1.2 强制转换 2. 运算符 二.JS语句1. 条件语句2. 循环语句 三.函数(方法)1. 声明函数的第一种方法2. 声明函数的第二种方法3. 声明函数的第三种方法 四.对象1. 对象的创建 -- 字面量2. 访问对象的属性3. 内置构造函数以…...

小北的技术博客:探索华为昇腾CANN训练营与AI技术创新——Ascend C算子开发能力认证考试(中级)

前言 哈喽哈喽,这里是zyll~,北浊.(大家可以亲切的呼唤我叫小北)智慧龙阁的创始人,一个在大数据和全站领域不断深耕的技术创作者。今天,我想和大家分享一些关于华为昇腾CANN训练营以及AI技术创新的最新资讯和实践经验~(初级证书还没拿到的小伙伴,可以先参考小北的这篇技术…...

Docker极速入门一文通

文章目录 Docker极速入门一文通Docker命令搜索镜像docker search拉取镜像|下载镜像docker pull查看镜像docker images删除镜像docker rmi运行容器docker run查看容器 docker ps删除容器 docker rm后台启动容器 docker run -d进入容器 docker exec拷贝文件到容器 docker cp拷贝容…...

Unity网络开发基础 —— 实践小项目

概述 接Unity网络开发基础 导入基础知识中的代码 需求分析 手动写Handler类 手动书写消息池 using GamePlayer; using System; using System.Collections; using System.Collections.Generic; using UnityEngine;/// <summary> /// 消息池中 主要是用于 注册 ID和消息类…...

四、Spring Boot集成Spring Security之认证流程

Spring Boot集成Spring Security之认证流程 一、概要说明二、基于内存的用户名密码1、默认用户名密码2、自定义用户名密码3、为方便测试添加测试接口TestController 三、登录登出重要概念介绍四、登录业务逻辑1、登录业务相关过滤器2、访问业务请求处理流程①、访问业务请求地址…...

Chromium 中chrome.bookmarks扩展接口c++实现

一、扩展接口定义 chrome.bookmarks 使用 chrome.bookmarks API 创建、整理以及以其他方式操纵书签。另请参阅覆盖网页&#xff08;可用于创建自定义“书签管理器”页面&#xff09;。 更多参考chrome.bookmarks | API | Chrome for Developers (google.cn) 扩展可以请从…...

编程思想:编程范式:响应式编程

文章目录 概述实现的设计模式举例总结概述 响应 响应一般指对于事件的响应,事件包括数据变化或其他事件 响应流程包括事件的发生,事件的传递,和事件的最终处理 事件在起点处发生,开始传递过程 传递过程,包括对事件的一系列处理,如事件封装的数据的类型转化,数据集合…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...