中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁(yè) > news >正文

w網(wǎng)站開(kāi)發(fā)文獻(xiàn)百度投訴中心在線申訴

w網(wǎng)站開(kāi)發(fā)文獻(xiàn),百度投訴中心在線申訴,臨沂哪里有做網(wǎng)站,主機(jī)屋 WordPress 問(wèn)題 多刷題的第二十九天,希望自己能夠不斷堅(jiān)持下去,迎來(lái)蛻變。😀😀😀 刷題語(yǔ)言:C Day29 任務(wù) ● 01背包問(wèn)題,你該了解這些! ● 01背包問(wèn)題,你該了解這些! 滾動(dòng)數(shù)組 …

刷題的第二十九天,希望自己能夠不斷堅(jiān)持下去,迎來(lái)蛻變。😀😀😀
刷題語(yǔ)言:C++
Day29 任務(wù)
● 01背包問(wèn)題,你該了解這些!
● 01背包問(wèn)題,你該了解這些! 滾動(dòng)數(shù)組
● 416. 分割等和子集

1 動(dòng)態(tài)規(guī)劃:01背包問(wèn)題,你該了解這些!

在這里插入圖片描述
背包問(wèn)題的理論基礎(chǔ)重中之重是01背包

1.1 01 背包

01 背包:有n件物品和一個(gè)最多能背重量為w的背包。第i件物品的重量是weight[i],得到的價(jià)值是value[i]。每件物品只能用一次,求解將哪些物品裝入背包里物品價(jià)值總和最大

在這里插入圖片描述

重量價(jià)值
物品0115
物品1320
物品2430

二維dp數(shù)組01背包
(1)確定dp數(shù)組以及下標(biāo)的含義
dp[i][j] 表示從下標(biāo)為[0-i]的物品里任意取,放進(jìn)容量為j的背包,價(jià)值總和最大是多少。
在這里插入圖片描述

(2)確定遞推公式

1.不放物品i:由dp[i - 1][j]推出,即背包容量為j,里面不放物品i的最大價(jià)值,此時(shí)dp[i][j]就是dp[i - 1][j]。(其實(shí)就是當(dāng)物品i的重量大于背包j的重量時(shí),物品i無(wú)法放進(jìn)背包中,所以背包內(nèi)的價(jià)值依然和前面相同。)
2.放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時(shí)候不放物品i的最大價(jià)值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的價(jià)值),就是背包放物品i得到的最大價(jià)值

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

(3)dp數(shù)組如何初始化

首先從dp[i][j]的定義出發(fā),如果背包容量j為0的話,即dp[i][0],無(wú)論是選取哪些物品,背包價(jià)值總和一定為0。如圖:
在這里插入圖片描述
狀態(tài)轉(zhuǎn)移方程是由 i-1 推導(dǎo)出來(lái),那么i為0的時(shí)候就一定要初始化
dp[0][j],即:i為0,存放編號(hào)0的物品的時(shí)候,各個(gè)容量的背包所能存放的最大價(jià)值。

那么很明顯當(dāng) j < weight[0]的時(shí)候,dp[0][j] 應(yīng)該是 0,因?yàn)楸嘲萘勘染幪?hào)0的物品重量還小。
當(dāng)j >= weight[0]時(shí),dp[0][j] 應(yīng)該是value[0],因?yàn)楸嘲萘糠抛銐蚍啪幪?hào)0物品

for (int j = 0; j < weight[0]; j++) {dp[0][j] = 0;
}
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}

在這里插入圖片描述
dp[0][j] 和 dp[i][0] 都已經(jīng)初始化,其他下標(biāo)的初始化什么數(shù)值都可以,因?yàn)槎紩?huì)被覆蓋。

vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}

(4)遍歷順序
在這里插入圖片描述
先遍歷物品,然后遍歷背包重量

for (int i = 1; i < weight.size(); i++) {for (int j = 0; j <= bagweight; j++) {if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}

先遍歷背包,再遍歷物品

// weight數(shù)組的大小 就是物品個(gè)數(shù)
for(int j = 0; j <= bagweight; j++) { // 遍歷背包容量for(int i = 1; i < weight.size(); i++) { // 遍歷物品if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}

(5)舉例推導(dǎo)dp數(shù)組
在這里插入圖片描述

C++:

void test_2_wei_bag_problem1() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagweight = 4;// 二維數(shù)組vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));// 初始化for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];}for (int i = 1; i < weight.size(); i++) {for (int j = 0; j <= bagweight; j++) {if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}cout << dp[weight.size() - 1][bagweight] << endl;    
}
int main() {test_2_wei_bag_problem1();
}

2 動(dòng)態(tài)規(guī)劃:01背包理論基礎(chǔ)(滾動(dòng)數(shù)組)

背包最大重量為4。

物品為:

重量價(jià)值
物品0115
物品1320
物品2430

一維dp數(shù)組:上一層可以重復(fù)利用,直接拷貝到當(dāng)前層。
dp[i][j] 表示從下標(biāo)為[0-i]的物品里任意取,放進(jìn)容量為j的背包,價(jià)值總和最大是多少。
(1)確定dp數(shù)組的定義
dp[j]表示:容量為j的背包,所背的物品價(jià)值可以最大為dp[j]
(2)一維dp數(shù)組的遞推公式

dp[j]有兩個(gè)選擇,一個(gè)是取自己dp[j] 相當(dāng)于 二維dp數(shù)組中的dp[i-1][j],即不放物品i,一個(gè)是取dp[j - weight[i]] + value[i],即放物品i,指定是取最大的,畢竟是求最大價(jià)值

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

(3)一維dp數(shù)組如何初始化
假設(shè)物品價(jià)值都是大于0的,所以dp數(shù)組初始化的時(shí)候,都初始為0
(4)一維dp數(shù)組遍歷順序

for (int i = 0; i < weight.size(); i++) {// 遍歷物品for (int j = bagweight; j >= weight[i]; j--) {// 遍歷背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

倒序遍歷是為了保證物品i只被放入一次! 如果一旦正序遍歷了,那么物品0就會(huì)被重復(fù)加入多次!

為什么二維dp數(shù)組遍歷的時(shí)候不用倒序呢?
因?yàn)閷?duì)于二維dp,dp[i][j]都是通過(guò)上一層即dp[i - 1][j]計(jì)算而來(lái),本層的dp[i][j]并不會(huì)被覆蓋!

(5)舉例推導(dǎo)dp數(shù)組
在這里插入圖片描述
C++:

void test_1_wei_bag_problem() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagWeight = 4;// 初始化vector<int> dp(bagWeight + 1, 0);for(int i = 0; i < weight.size(); i++) { // 遍歷物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bagWeight] << endl;
}int main() {test_1_wei_bag_problem();
}

3 分割等和子集

416. 分割等和子集
在這里插入圖片描述
思路:
背包問(wèn)題,有N件物品和一個(gè)最多能背重量為W 的背包。第i件物品的重量是weight[i],得到的價(jià)值是value[i] 。每件物品只能用一次,求解將哪些物品裝入背包里物品價(jià)值總和最大。

本題使用的是01背包,因?yàn)樵匚覀冎荒苡靡淮巍?br /> 把01背包問(wèn)題套到本題:
(1)背包的體積為sum / 2
(2)背包要放入的商品(集合里的元素)重量為 元素的數(shù)值,價(jià)值也為元素的數(shù)值
(3)背包如果正好裝滿,說(shuō)明找到了總和為 sum / 2 的子集。
(4)背包中每一個(gè)元素是不可重復(fù)放入。

動(dòng)態(tài)規(guī)劃
(1)確定dp數(shù)組以及下標(biāo)的含義
01背包中,dp[j] 表示: 容量為j的背包,所背的物品價(jià)值最大可以為dp[j]
本題:dp[j]表示 背包總?cè)萘?#xff08;所能裝的總重量)是j,放進(jìn)物品后,背的最大重量為dp[j]
(2)確定遞推公式

01背包的遞推公式為:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本題,相當(dāng)于背包里放入數(shù)值,那么物品i的重量是nums[i],其價(jià)值也是nums[i]。
所以遞推公式:dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

(3)dp數(shù)組如何初始化

dp[0]一定是0。
如果題目給的價(jià)值都是正整數(shù)那么非0下標(biāo)都初始化為0就可以了,如果題目給的價(jià)值有負(fù)數(shù),那么非0下標(biāo)就要初始化為負(fù)無(wú)窮。
這樣才能讓dp數(shù)組在遞推的過(guò)程中取得最大的價(jià)值,而不是被初始值覆蓋了

(4)確定遍歷順序

for (int i = 0; i < nums.size(); i++) {for (int j = target; j >= nums[i]; j--) {// 每一個(gè)元素一定是不可重復(fù)放入,所以從大到小遍歷dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}
}

(5)舉例推導(dǎo)dp數(shù)組
dp[j]的數(shù)值一定是小于等于j的,如果dp[j] == j 說(shuō)明,集合中的子集總和正好可以湊成總和j
在這里插入圖片描述
C++:

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;vector<int> dp(10001, 0);for (int i = 0; i < nums.size(); i++) {sum += nums[i];}if (sum % 2 == 1) return false;int target = sum / 2;// 開(kāi)始 01背包for(int i = 0; i < nums.size(); i++) {for(int j = target; j >= nums[i]; j--) { // 每一個(gè)元素一定是不可重復(fù)放入,所以從大到小遍歷dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}// 集合中的元素正好可以湊成總和targetif (dp[target] == target) return true;return false;}
};

時(shí)間復(fù)雜度: O ( n 2 ) O(n^2) O(n2)
空間復(fù)雜度: O ( n ) O(n) O(n),雖然dp數(shù)組大小為一個(gè)常數(shù),但是大常數(shù)


鼓勵(lì)堅(jiān)持三十天的自己😀😀😀

http://www.risenshineclean.com/news/22035.html

相關(guān)文章:

  • 紹興優(yōu)秀做網(wǎng)站的蘇州網(wǎng)站維護(hù)
  • it行業(yè)做網(wǎng)站一個(gè)月多少錢(qián)中國(guó)推廣網(wǎng)站
  • 用ecshop的網(wǎng)站西地那非片能延時(shí)多久有副作用嗎
  • 網(wǎng)站推廣方案途徑網(wǎng)站設(shè)計(jì)公司怎么樣
  • ubuntu apache php mysql wordpress某個(gè)網(wǎng)站seo分析實(shí)例
  • 網(wǎng)頁(yè)設(shè)計(jì)站點(diǎn)規(guī)劃蘇州seo營(yíng)銷
  • 免費(fèi)的網(wǎng)頁(yè)設(shè)計(jì)成品詳解seo黑帽教學(xué)網(wǎng)
  • 大連省建設(shè)廳網(wǎng)站seo研究中心教程
  • 網(wǎng)站建設(shè)企業(yè) 熊賬號(hào)aso優(yōu)化app推廣
  • 北京網(wǎng)站建設(shè)天下公司網(wǎng)絡(luò)推廣營(yíng)銷方式
  • 如何在建設(shè)銀行網(wǎng)站查驗(yàn)回單全國(guó)免費(fèi)發(fā)布信息平臺(tái)
  • 做網(wǎng)站賺幾百萬(wàn)媒體網(wǎng)站
  • wordpress添加搜索插件北京seo顧問(wèn)服務(wù)
  • 本網(wǎng)站服務(wù)器設(shè)在美國(guó)服務(wù)器保護(hù)友情鏈接交易平臺(tái)源碼
  • 網(wǎng)站備案和服務(wù)器備案嗎北京seo站內(nèi)優(yōu)化
  • 備案號(hào)鏈接工信部網(wǎng)站免費(fèi)創(chuàng)建個(gè)人博客網(wǎng)站
  • 江蘇建設(shè)集團(tuán)有限公司董事長(zhǎng)seo網(wǎng)絡(luò)排名優(yōu)化方法
  • 濟(jì)寧網(wǎng)站建設(shè)神華科技推廣網(wǎng)站多少錢(qián)
  • 購(gòu)物網(wǎng)站建設(shè) 屬于信息系統(tǒng)管理與設(shè)計(jì)么?百度網(wǎng)頁(yè)入口
  • 高端網(wǎng)站制作上海軟文素材
  • 網(wǎng)站集成微信登錄seo數(shù)據(jù)
  • 網(wǎng)站建設(shè)建設(shè)百度學(xué)術(shù)論文查重官網(wǎng)
  • wordpress 軍事主題快速網(wǎng)站排名優(yōu)化
  • 云南網(wǎng)站設(shè)計(jì)外包注冊(cè)公司流程和費(fèi)用
  • 萊蕪區(qū)宣傳部網(wǎng)站seo排名優(yōu)化
  • 網(wǎng)站什么也沒(méi)動(dòng)怎么不收錄啦免費(fèi)入駐的電商平臺(tái)
  • 怎么做社交網(wǎng)站日本積分榜最新排名
  • 網(wǎng)站還沒(méi)上線怎么做品牌推廣友情鏈接的四個(gè)技巧
  • 哪有做網(wǎng)站的公司b站推廣網(wǎng)站入口2023的推廣形式
  • 蚌埠網(wǎng)站制作哪家好如何搭建個(gè)人網(wǎng)站