保山市建设厅网站,网站制作的大公司,wordpress首页友情链接,廊坊做网站公司目录
01背包問題 - DP二維數組
01 背包問題描述
暴力解
動態規劃
確認DP數組以及下標的含意
確定遞推公式
01背包问题 一维
一维DP 数組(滾動数組)
動態規劃五部曲
定義DP数組以及其下標含意
遞推公式
初始化
遍歷順序
讀題
416. 分割等和子集
自己看到题目的第…目录
01背包問題 - DP二維數組
01 背包問題描述
暴力解
動態規劃
確認DP數組以及下標的含意
確定遞推公式
01背包问题 一维
一维DP 数組(滾動数組)
動態規劃五部曲
定義DP数組以及其下標含意
遞推公式
初始化
遍歷順序
讀題
416. 分割等和子集
自己看到题目的第一想法
看完代码随想录之后的想法
416. 分割等和子集- 實作
思路
Code
總結
自己实现过程中遇到哪些困难
今日收获记录一下自己的学习时长
相關資料 01背包問題 - DP二維數組
01 背包問題描述
背包最高可承重重量為j有i件物品每件物品的重量為weight[i]並且對應的價值為value[i]每件物品只能用一次
背包放入那些物品可以達到最高的價值
01 的含意就是每件物品只能用一次取(1)或不取(0)
暴力解
01背包問題可以使用暴力解來解出來就是去窮舉每一個東西取或不取最後找出最大的價值和
可以使用回溯算法去做但時間複雜度會是 $O(2^n)$
動態規劃
確認DP數組以及下標的含意
dp[i][j]: [0, i]物品任意取可放進容量為j的背包的最大價值。
確定遞推公式
在描述中物品有兩種狀態一個是不放入背包一個是放入背包
物品i 不放入背包: 代表我們要知道的是當下的i不放入背包j的最大價值是多少那就是dp[i - 1][j]背包容量為j在不放入i之前最大的是i - 1所以得出dp[i - 1][j]物品i放入背包: 代表我們要知道當下物品i放入背包之後剩餘的背包重量可得到最大的價值是多少: dp[i - 1][j - weight[i]]這代表的是背包可承重的重量為j 減去目前i的重量weight[i]並且不包含當前i的重量最後再加入value[i] 代表當前的價值加上扣除當前重量的背包所能得到的最大價值。最後整合為dp[i - 1][j - weight[i]] value[i]
那我們是要取最大的數值所以遞推公式會變成 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i] value[i]); 01背包问题 一维
一维DP 数組(滾動数組)
藉由壓縮dp[i - 1] 到dp[i] 因為在二維的DP遞推方程裡是dp[i][j] max( dp[i - 1][j], dp[i - 1][j - weight[i] value[i])
假設壓縮成一维數組可以看成假設dp[j]跟dp[j - weight[i]] value[i] 不用將上一層拷貝而是透過不斷更新dp[j] 來比較值。
其狀態就像是滾動著更新我們的dp数組值透過維護dp[j]的遍歷順序來維護裡面的值與dp二維数組一致
動態規劃五部曲
定義DP数組以及其下標含意
dp[j]: 背包重量為j的最大價值為dp[j]
遞推公式
與二维數組一樣dp[j]的數值可以透過當前dpj 以及dp[j - weighti 兩者做比較。
所以遞推公式可以將i去除掉變成
dp[j] max(dp[j], dp[j - weight[i]] value[i]);
初始化
dp数組在dp[0]時根據定義需要將dp[0]初始化為0並且根據遞推公式每次都會取最大值所以其他数值也應該初始化為dp数組中最小的值也就是0
所以在初始化時將dp数組全部初始化為0
遍歷順序
在二维數組中每一層的數值都是當前位置的正上方以及左上方的數據得出
從二维壓縮成一维數組我們需要模擬二维數組的方式
所以根據我們的遞推公式我們不能使用正序遍歷不然原本在二维數組中左上方的數據就會被覆蓋掉
而使用倒序可以保證每一層的數據都是由二维數組上一層正上方以及左上方得出的。
透過倒敘更新確保了在考慮當前物品時dp[j - weight[i]]仍然代表前一個物品的狀態但是如果使用正序那dp[j - weight[i]]就會被提早更新了
如下
假設我們有以下物品和背包
物品重量: w [2,3] 物品價值: v [3,4] 背包最大容量: W 5 使用一維數組正序更新時 物品\\背包 | 0 | 1 | 2 | 3 | 4 | 5 | 進行的操作
----------------------------------- ------------ | 0 | 0 | 0 | 0 | 0 | 0 | 初始化2 | 0 | 0 | 3 | 3 | 3 | 3 | 考慮物品1 (w2, v3)3 | 0 | 0 | 3 | 4 | 7 | 7 | 考慮物品2 (w3, v4)當我們考慮物品2時對於背包容量4dp[4]是基於dp[1]已被更新的和dp[4-w[2]1]計算 使用一維數組倒序更新時 物品\\背包 | 0 | 1 | 2 | 3 | 4 | 5 | 進行的操作
----------------------------------- ------------ | 0 | 0 | 0 | 0 | 0 | 0 | 初始化2 | 0 | 0 | 3 | 3 | 3 | 3 | 考慮物品1 (w2, v3)3 | 0 | 0 | 3 | 4 | 5 | 7 | 考慮物品2 (w3, v4)當我們考慮物品2和背包容量4時dp[4]是基於dp[1]尚未更新的和dp[4-w[2]1]計算的
在影片講解的部分有個彈幕寫了以下這段分享給你 一维数组就像走楼梯你去二楼就必须从一楼上去三楼也要从一楼走倒叙就还好比下楼想去几楼都不用重复路过其他楼层。 並且需要先遍歷物品在遍歷背包因為需要上一個物品的值如果先遍歷背包則只抓到一個物品的值。 讀題
416. 分割等和子集
自己看到题目的第一想法
看完跟01背包問題沒有辦法有很直接的連結我大致有想到一個是dp[i][j]代表的是[0 ~ i][j ~ size()]的區間是否相等但感覺有些地方沒有想清楚先看題解。
看完代码随想录之后的想法
想法很巧妙如果有一個背包等於所有和的一半剩下的元素相加也等於剩餘的一半 dp[j]: 容量為j的背包最大價值為dp[j]並且數組中的重量跟價值可以看成是一致的
並判斷dp[target] target。dp数組初始化為0 並且背包重量設為target 1
忘記思考到target如果不能被2整除那就是要return false。 416. 分割等和子集- 實作
思路 定義DP數組以及下標的含意 target: 假設子序和的重量為總和的一半那代表另一半為剩餘的一半。 假設總和除2餘1代表不會有一個子序和等於另一個子序和 dp[j] : 背包重量 j 的最大價值為dp[j] nums数組中重量與價值就是nums[i] 遞推公式 dp[j] max(dp[j], dp[j - nums[i]] nums[i]); 根據遞推公式確定DP數組如何初始化 dp[0]要初始化為0其他部分也要更新為正整數下的最小位数0 確定遍歷順序 避免覆蓋掉上一次的值所以要使用倒敘遍歷 打印dp數組 (debug);
Code
class Solution {
public:bool canPartition(vectorint nums) {int target 0;for(int i 0; i nums.size(); i) {target nums[i];}if (target % 2 1) return false;target / 2;vectorint dp(target 1, 0);for(int i 0; i nums.size(); i) {for(int j target; j nums[i]; j--) {dp[j] max(dp[j], dp[j - nums[i]] nums[i]);}if(dp[target] target) return true;}return false;}
};總結
自己实现过程中遇到哪些困难
困難點主要是在思考二维數組壓縮成一维數組的部分這個部分思考比較久並且在416分割等和子集中也是遇到了點問題在思考上沒有想到nums[i]是重量與價值相等彈點通之後就比較理解了
今日收获记录一下自己的学习时长
今天大概學了3hr主要是在理解01背包的思維與想法。
相關資料
● 今日学习的文章链接和视频链接
算法圖解
01背包问题 二维
https://programmercarl.com/背包理论基础01背包-1.html
视频讲解带你学透0-1背包问题| 关于背包问题你不清楚的地方这里都讲了| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili
01背包问题 一维
https://programmercarl.com/背包理论基础01背包-2.html
视频讲解带你学透01背包问题滚动数组篇 | 从此对背包问题不再迷茫_哔哩哔哩_bilibili
416. 分割等和子集
本题是 01背包的应用类题目
https://programmercarl.com/0416.分割等和子集.html
视频讲解动态规划之背包问题这个包能装满吗| LeetCode416.分割等和子集_哔哩哔哩_bilibili
