算法設計與分析5(動態規劃)

動態規劃的基本思想

將一個問題劃分為多個不獨立的子問題,這些子問題在求解過程中可能會有些數據進行了重復計算。我們可以把計算過的數據保存起來,當下次遇到同樣的數據計算時,就可以查表直接得到答案,而不是再次計算

動態規劃的例子

找兩個字符串匹配的編輯距離

字符串的編輯距離,又稱為Levenshtein距離,是指利用字符操作,把字符串A轉換成字符串B所需要的最少操作數。操作包括增刪改
**問題:**給定兩個字符串A:sun和B:sautr,求字符串A至少經過多少步字符操作變成字符串B
解:
用<i,j>表示字符串A長為i,字符串B長為j的字符串編輯距離
對兩個字符串,最末位字符進行討論
相同:那么末位字符不需要進行操作,那么<i,j>=<i-1,j-1>
不相同:
可以做三種操作:
Ⅰ:增加一個字符:
增加后,末尾字符相同,問題變成i+1長的字符串A與j長的字符串B匹配
<i,j>=<i+1,j>+1,+1是此次做的增加操作
又由上可知<i,j>=<i-1,j-1>,所以
<i,j>=<i,j-1>+1
Ⅱ:刪
同理,<i,j>=<i-1,j>+1
Ⅲ:改
同理,<i,j>=<i-1,j-1>+1
做矩陣圖,<i,j>框內數字表示A前i個字符與B前j個字符匹配時,最小修改次數,由圖可知,確定它的最小值,如果末尾字符相同,則等于左側對角線值,不相等,則從周圍三個數值中,選最小的+1

在這里插入圖片描述

背包問題

**問題:**有n個物品,它們有各自的體積和價值,現有給定容量的背包,如何讓背包里裝入的物品具有最大的價值總和?
假設現在有四個物品,背包容量為8

i(編號) 1 2 3 4
w(體積) 2 3 4 5
v(價值) 3 4 5 6

解:
矩陣圖中<i,j>表示從下標為 [0 - i] 的物品里任意取,放進容量為j的背包,價值總和最大是多少。
每次我們有兩種選擇:
將物品放入背包:加該物品的重量和價值
不放入:保持原來的數值
如果容量為3,可以選擇的物品有1,2,3
那么我們只需要比較<i-1,j>,<i-1,j-w(i))>+v(i)
其中<i-1,j>表示不裝該物品,<i-1,j-w(i))>+v(i) 表示裝了該商品,背包容量減少w(i),但價值增加了v(i);
取兩者中最大值即可
在這里插入圖片描述

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/diannao/76744.shtml
繁體地址,請注明出處:http://hk.pswp.cn/diannao/76744.shtml
英文地址,請注明出處:http://en.pswp.cn/diannao/76744.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

怎么理解量子比特模型,遷移到量子計算機開始編程

怎么理解量子比特模型&#xff0c;遷移到量子計算機開始編程 視頻鏈接&#xff1a; 好的現在是2025年的3月最后一天,3月31號,今天我們討論的話題是量子編程,也就是在量子計算機上,使用特定的語言進行軟件開發。當然我們要討論的,不是,量子編程的某一門語言的技術細節,而是考慮…

使用Expo框架開發APP——詳細教程

在移動應用開發日益普及的今天&#xff0c;跨平臺開發工具越來越受到開發者青睞。Expo 是基于 React Native 的一整套工具和服務&#xff0c;它能夠大幅降低原生開發的門檻&#xff0c;讓開發者只需關注業務邏輯和界面實現&#xff0c;而不用糾結于復雜的原生配置。本文將從零開…

windows技術基礎知識

NT架構 NT 就是new techonology 的英文單詞縮寫&#xff0c;是微軟1993年推出操作系統的重大升級&#xff0c;如內存管理&#xff0c;安全機制&#xff0c;多任務&#xff0c;多線程支持。在此之前操作系統都是基于MS-DOS上面的圖形化界面&#xff0c;只有有限的內存管理和多任…

迪杰斯特拉+二分+優先隊列+拓撲+堆優化(奶牛航線Cowroute、架設電話線dd、路障Roadblocks、奶牛交通Traffic)

原文地址 https://fmcraft.top/index.php/Programming/2025040402.html 主要算法 迪杰斯特拉Dijkstra 題目列表 P1&#xff1a;奶牛航線Cowroute 題目描述 題目描述 Bessie已經厭倦了農場冬天的寒冷氣候&#xff0c;她決定坐飛機去更溫暖的地方去度假。不幸的是&#xf…

#Liunx內存管理# 在32bit Linux內核中,用戶空間和內核空間的比例通常是3:1,可以修改成2:2嗎?

在32位Linux內核中&#xff0c;用戶空間和內核空間的3:1默認比例可以修改為2:2&#xff0c;但需要權衡實際需求和潛在影響。以下是具體分析&#xff1a; 一、修改可行性 1.技術實現 通過內核啟動參數調整虛擬地址空間劃分&#xff0c;例如在GRUB配置中添加mem2G參數&#xff0c…

JAVA:使用 Curator 進行 ZooKeeper 操作的技術指南

1、簡述 Apache Curator 是一個基于 ZooKeeper 的 Java 客戶端庫&#xff0c;它極大地簡化了使用 ZooKeeper 的開發工作。Curator 提供了高層次的 API&#xff0c;封裝了很多復雜的 ZooKeeper 操作&#xff0c;例如連接管理、分布式鎖、Leader 選舉等。 在分布式系統中&#…

Julia語言的測試覆蓋率

Julia語言的測試覆蓋率探討 引言 在現代軟件開發中&#xff0c;測試是確保軟件質量的重要環節。隨著軟件的復雜度不斷增加&#xff0c;測試覆蓋率作為衡量測試質量的一個重要指標&#xff0c;受到了越來越多開發者的關注。Julia語言作為一種高性能的動態編程語言&#xff0c;…

【萬字總結】前端全方位性能優化指南(八)——Webpack 6調優、模塊聯邦升級、Tree Shaking突破

構建工具深度優化——從機械配置到智能工程革命 當Webpack配置項突破2000行、Node進程內存耗盡告警時,傳統構建優化已觸及工具鏈的物理極限:Babel轉譯耗時占比超60%、跨項目模塊復用催生冗余構建、Tree Shaking誤刪關鍵代碼引發線上事故……構建流程正從「工程問題」演變為「…

使用MCP服務器實現AI任務完成通知:讓Cursor更智能

0. 簡介 在使用AI工具進行長時間任務時&#xff0c;常常需要等待結果。MCP&#xff08;Model Context Protocol&#xff09;服務器"mcp_server_notify"提供了一個優雅的解決方案&#xff0c;讓AI在完成任務后通過系統通知提醒你。本文將介紹如何在Cursor中配置和使用…

Java面試黃金寶典33

1. 什么是存取控制、 觸發器、 存儲過程 、 游標 存取控制 定義&#xff1a;存取控制是數據庫管理系統&#xff08;DBMS&#xff09;為保障數據安全性與完整性&#xff0c;對不同用戶訪問數據庫對象&#xff08;如表、視圖等&#xff09;的權限加以管理的機制。它借助定義用戶…

DataX實戰教程

需求&#xff1a; 用datax同步mysql&#xff1a; 192.168.236.134中test1庫的user表到192.168.236.136中test1庫的user表 步驟&#xff1a; 下載安裝包 https://github.com/alibaba/DataX/blob/master/userGuid.md 進入引導頁 https://github.com/alibaba/DataX/blob/ma…

C#/.NET/.NET Core技術前沿周刊 | 第 32 期(2025年3.24-3.31)

前言 C#/.NET/.NET Core技術前沿周刊&#xff0c;你的每周技術指南針&#xff01;記錄、追蹤C#/.NET/.NET Core領域、生態的每周最新、最實用、最有價值的技術文章、社區動態、優質項目和學習資源等。讓你時刻站在技術前沿&#xff0c;助力技術成長與視野拓寬。 歡迎投稿、推薦…

c++基礎-----c++ 成員變量初始化順序

操作系統&#xff1a;ubuntu22.04 IDE:Visual Studio Code 編程語言&#xff1a;C11 描述 在C中&#xff0c;類的成員變量初始化的順序是由它們在類中聲明的順序決定的&#xff0c;而不是由它們在構造函數初始化列表中的順序決定的。這意味著無論你在構造函數初始化列表中如何…

Pascal語言的貪心算法

貪心算法與Pascal語言 引言 在算法設計與分析中&#xff0c;貪心算法是一類重要的算法策略。它以一種直接而高效的方式解決問題&#xff0c;尤其適合那些可以通過局部最優解推導出全局最優解的問題。在本文中&#xff0c;我們將探討貪心算法的基本概念、工作原理及其在Pascal…

Sensodrive力控關節模組SensoJoint:TüV安全認證助力機器人開發

在機器人技術領域&#xff0c;安全性和開發效率是行業關注的重點。SensoDrive的SensoJoint 機器人力控關節模組&#xff0c;憑借其可靠的安全性能和高效的開發優勢&#xff0c;正在為機器人開發提供有力支持。 2025年3月31日&#xff0c;SensoDrive的 SensoJoint 力控關節模組獲…

自動駕駛04:點云預處理03

點云組幀 感知算法人員在完成點云的運動畸變補償后&#xff0c;會發現一個問題&#xff1a;激光雷達發送的點云數據包中的點云數量其實非常少&#xff0c;完全無法用來進行后續感知和定位層面的處理工作。 此時&#xff0c;感知算法人員就需要對這些數據包進行點云組幀的處理…

棧回溯和離線斷點

棧回溯和離線斷點 棧回溯&#xff08;Stack Backtrace&#xff09; 棧回溯是一種重建函數調用鏈的技術&#xff0c;對于分析棧溢出的根本原因非常有價值。 實現方式 // 簡單的棧回溯實現示例&#xff08;ARM Cortex-M架構&#xff09; void stack_backtrace(void) {uint32_…

Vue3學習二

認識組件的嵌套 還可以將Main中內容再劃分 scoped防止組件與組件之間的樣式相互污染 組件的通信 父子組件之間通信的方式 父組件傳遞給子組件 給傳過來的內容做限制 type為傳的內容的屬性類型&#xff0c;required為true表示該內容是必須傳的&#xff0c;default為&#xff0c…

配置文件 yaml

文章目錄 一、yaml簡介二、YAML 文件基本語法1.縮進2.鍵值對3.注釋4.支持多種數據類型5.示例 YML 文件 三、YAML 文件的基本元素&#xff1a;純量、對象、數組1.純量(scalars)(1)布爾值(Booleans)(2)Null 值 2.對象(Object) / 映射(Mapping) / 字典(Dictionaries) / 鍵值對(Key…

antvX6自定義 HTML 節點創建與更新教程

自定義 HTML 節點創建與更新教程 本文詳細介紹如何利用 HTML、CSS 和 JavaScript 創建自定義節點&#xff0c;并通過動態更新節點數據來改變節點顯示效果。無論你是否有前端基礎&#xff0c;都能輕松跟著本教程一步步實現。 1. 基礎樣式設置 首先&#xff0c;使用 CSS 定義基…