Javascript动态规划算法
JavaScript中的动态规划(Dynamic Programming,简称DP)是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它主要致力于将“合适”的问题拆分成更小的子目标,并通过建立状态转移方程、缓存并复用以往结果以及按顺序从小往大算这三个步骤来解决问题。以下是对js动态规划算法的详细解析:
一、动态规划的基本概念
- 状态转移方程:动态规划的核心是找到一个能够描述问题状态转移的数学方程,即状态转移方程。这个方程描述了如何从较小的子问题的解推导出较大问题的解。
- 缓存并复用以往结果:为了避免重复计算,动态规划会将已经计算过的子问题的解存储起来,以便在后续的计算中直接引用。这通常通过一个数组或对象来实现,称为DP表。
- 按顺序从小往大算:动态规划通常按照某种顺序(如从小到大的子问题规模)来计算子问题的解,并最终得到原问题的解。
二、动态规划的应用示例
- 斐波那契数列
斐波那契数列是一个经典的动态规划问题。数列中的每个数字是前两个数字之和,通常以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数组用于存储已经计算过的斐波那契数,从而避免了重复计算。
- 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(', ')}`);
三、动态规划的优点和局限性
-
优点:
- 能够高效地解决具有重叠子问题的问题。
- 通过缓存和复用以往结果,避免了大量的重复计算。
-
局限性:
- 只适用于具有最优子结构和重叠子问题的问题。
- 对于某些问题,可能需要大量的空间来存储子问题的解(即DP表)。
四、总结
JavaScript中的动态规划是一种强大的算法设计范式,适用于解决具有重叠子问题的问题。通过建立状态转移方程、缓存并复用以往结果以及按顺序从小往大算这三个步骤,可以高效地求解复杂问题。然而,动态规划也有一定的局限性,只适用于具有最优子结构和重叠子问题的问题。在实际应用中,需要根据问题的特点选择合适的算法设计范式来求解。
相关文章:

Javascript动态规划算法
JavaScript中的动态规划(Dynamic Programming,简称DP)是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它主要致力于将“合适”的问题拆分成更小的子目标,并通过建立状态转移方程、缓存并复用以往结果以及按…...
Java 循环里怎么删除元素才安全
首先 在 Java 中,当你在循环中遍历集合时,直接删除元素可能会引发 ConcurrentModificationException。为了安全地删除元素,推荐使用 Iterator 来进行删除操作。 以下是使用 Iterator 删除元素的常见模式: import java.util.Arr…...
LabVIEW晶体振荡器自动化测试系统
基于LabVIEW平台的晶体振荡器自动化测试系统解决了传统手工测试晶体振荡器繁琐且易出错的问题。该系统通过高度自动化的测试流程,提高了测试效率和精度,实现了数据的自动采集与处理,适用于电子、通信等领域的晶振测试需求。 项目背景与意义 …...

3.6.xx版本SpringBoot创建基于Swagger接口文档
介绍 基于Swagger构建的JavaAPI文档工具,实现后端功能的测试,并撰写API接口文档。 方法 pom.xml中引入依赖,要注意的是,本依赖使用的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 源码编译安装详解:跨平台指南及完整步骤解析 文章目录 Python 源码编译安装详解:跨平台指南及完整步骤解析一 准备工作1)Ubuntu/Debian2)CentOS/RHEL3)macOS 二 下载 Python 源码三 编译与安装1)解压…...

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

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

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

【vue】监听table水平滚动条切换tab后还原位置
有个需求就是切换tab后,原先的table水平滚动条要还原位置(如下图),先说下思路,大致就是 切出页面时 把滚动距离保存到Storage 中,切回来时在恢复 直接上代码 首先table ref指定一下ref"jtable" …...
C#使用PdfSharp生成PDF文件实例详解
许多项目开发中需要生成PDF, 常规办法使用官方提供的Microsoft.Office.Interop.Worddll插件,但是这种方法需要完全安装OFFICE,另外版本不一致还会出现很多错误。一般不推荐使用。 下面介绍几种巧妙的用法,定能事半功倍。 本文使用PDFsharp完成功能。 PDFsharp一款开源的…...

【软件系统架构设计师-案例-1】架构风格
1. 请用200字以内说明系统可靠性的定义及包含的4个子特性,并简要指出提高系统可靠性一般采用哪些技术? (1)可靠性定义:系统在规定的时间或环境条件下,完成规定功能的能力,就是系统无故障运行的…...

神经网络整体架构
文章目录 1.输入层Input2.卷积层Conv3.激活函数层(一)Sigmoid 函数(二)Tanh 函数(三)修正线性单元ReLU(四)Leaky ReLU函数(带泄露的Relu)(五)参数化ReLU 4.池化层POOL5.全连接层FC6.输出层Output 用全连接神经网络处理大尺寸图像具有三个明显的缺点: ①将图像展开为…...
山西农业大学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 创建、整理以及以其他方式操纵书签。另请参阅覆盖网页(可用于创建自定义“书签管理器”页面)。 更多参考chrome.bookmarks | API | Chrome for Developers (google.cn) 扩展可以请从…...
编程思想:编程范式:响应式编程
文章目录 概述实现的设计模式举例总结概述 响应 响应一般指对于事件的响应,事件包括数据变化或其他事件 响应流程包括事件的发生,事件的传递,和事件的最终处理 事件在起点处发生,开始传递过程 传递过程,包括对事件的一系列处理,如事件封装的数据的类型转化,数据集合…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...

让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

无头浏览器技术:Python爬虫如何精准模拟搜索点击
1. 无头浏览器技术概述 1.1 什么是无头浏览器? 无头浏览器是一种没有图形用户界面(GUI)的浏览器,它通过程序控制浏览器内核(如Chromium、Firefox)执行页面加载、JavaScript渲染、表单提交等操作。由于不渲…...
Go爬虫开发学习记录
Go爬虫开发学习记录 基础篇:使用net/http库 Go的标准库net/http提供了完善的HTTP客户端功能,是构建爬虫的基石: package mainimport ("fmt""io""net/http" )func fetchPage(url string) string {// 创建自定…...