當前位置:網站首頁>01背包(動態規劃)小結
01背包(動態規劃)小結
2022-01-27 17:10:38 【別搶我的辣條~】
一,問題
【問題】
一個容量為m公斤的背包。現有n種物品,每種物品只有一件,它們的重量分別為w[ i ](1<=i<=n),它們的價值分別為c[ i ](1<=i<=n)。求能放入背包的最大價值。
【輸入】
第一行:兩個整數,n(物品數量,n<51)和m(背包容量,m<201)。
第2,3,,,n+1行:每行兩個整數w[i],c[i],錶示每個物品的重量和價值。
【輸出】
一個數,錶示最大價值。
【樣例輸入】
3 6
3 5
2 3
4 6
【樣例輸出】
9
PS:
01背包:第 i 件物品可以放入0個或1個;
完全背包:第 i 件物品可以放入0個,1個,2個.........
二,解答思路
1,確定狀態變量(函數);
2,確定狀態轉移方程(遞推關系);
3,確定邊界條件。
最大價值是物品數量 i 和背包容量 j 的函數。
設函數 f[ i ][ j ] 錶示前 i 件物品放入容量為 j 的背包的最大價值。
最終的最大價值就是物品數量 i 從0增長到n,背包容量 j 從0增長到m時的 f[ n ][ m ] 的值。
若當前背包容量為 j ,我們就要考慮第 i 件物品能否放入?是否放入?
1,當前背包容量 j<W[i], 不能放入,則 f[ i [ j ]=f[ i-1 ][ j ];
2,當前背包容量 j>=W[i],能放入,但要比較價值:
(1)如果第 i 件物品不放入背包,則 f[ i ][ j ]=f[i-1][ j ];
(2)如果第 i 件物品放入背包,則f[ i ][ j ]=f[ i -1 ][ j-w[ i ] ]+c[ i ]
如果第 i 件物品放入背包,則背包容量還剩 j-w[ i ],所以要取前 i-1 件物品放入背包,剩餘容量 j-w[ i ]所獲得的最大價值為 f[ i-1 ][ j-w[i] ]。
舉個例子:
狀態轉移方程:
f[ i ][ j ]=f[ i-1 ][ j ],(j<w[ i ])
f[ i ][ j ]=max(f[ i-1 ][ j ],f[ i-1 ][ j-w[i] ]+c[ i ],(j>=w[ i ])
邊界條件:f[ i ][ j ]=0
三,代碼
for(i=1;i<=n;i++)//物品 i
{
for(j=1;j<=m;j++)//容量 j
{
if(j<w[i])
f[i][j]=f[i-1][j];
else
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
}
}
printf("%d",f[n][m]);
作進一步的優化:
用一維數組 f[ j ] 只記錄一行數據。讓 j 值順序循環,順序更新 f[ j ] 的值。
最終簡化為:
for(i=1;i<=n;i++)//物品 i
{
for(j=w[i];j<=m;j++)//容量 j
{
f[j]=max(f[j],f[j-w[i]]+c[i]);
}
}
printf("%d",f[m]);
因為 j 是逆序循環,f[ j ]會先於 f[ j-w[i] ]更新,也就是說,用舊值 f[ j-w[i] ]去更新 f[ j ],相當於用上一行的 f[ j-w[i] ]去更新 f[ j ]。
版權聲明
本文為[別搶我的辣條~]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201271710382382.html
邊欄推薦
- 編輯vim時突然大部分鍵失靈,只剩下空格還能用時,猜猜原因?
- cmseasy&內網滲透 Writeup
- 南開大學 | AbiU-Net:基於Transformer的非對稱雙邊U-Net提昇顯著性目標檢測
- 活久見!TCP兩次揮手,你見過嗎?那四次握手呢?
- MQL5-RPC來自 MQL5 的遠程過程調用
- Oracle(四):和SQL*Plus命令來場邂逅
- stm32+mpu6050+四元數解算
- ScheduledExecutorService scheduleAtFixedRate、scheduleWithFixedDelay以及創建定時心跳
- 太難為我這個應届生了,騰訊面試了8輪,終拿下騰訊Android測發崗offer(1)
- 跨文化研究:遊戲可能在維持文化多樣性方面扮演著重要角色
猜你喜歡
隨機推薦
- uniapp上傳圖片及組件傳值
- php獲取gmt時間及時區修改
- lnmp 三之haproxy的使用
- 華為手機USB連不上電腦的解决方法
- Flutter 2,移動金融應用開發
- 關於st25系列NFC標簽簡單介紹及st25TV系列用於門禁讀取時的注意事項總結
- Alink & FlinkMLlib 文章匯總
- 關於用ffmpeg轉手機視頻發現視頻長寬倒了的問題
- 函數 / 類模板--模板2
- NoNodeAvailableException[None of the configured nodes are available: [{#transport#-1}····
- 一場面試結束,某度員工從事Android 5年為何還是初級工程師?
- 3本書閱讀筆記【人月神話-Go語言實戰-研發能力持續成長路線】01
- PHP垃圾回收機制
- 快樂寒假 22/01/20
- 解决延遲有 Wi-Fi 6 就够了!(家裏的 Wi)
- 【ISO15765_UDS&OBD診斷】-01-概述
- 【Mysql上分之路】第九篇:Mysql存儲引擎
- 【Unity Shader】HDRP下Amplify Shader Editor透明物體排序不正確
- yum -bash: /usr/bin/yum: /usr/bin/: bad interpreter: Permission denied
- 惡意軟件分析實戰20-內核級軟件逆向Lab10-2
- RHCE 第一次作業
- 220121--測試用例
- [渝粵教育] 華中農業大學 經濟學原理 參考 資料
- nuxt項目總結-綜合
- C語言第一課
- 各比特大佬,Spark的重點難點系列暫時更新完畢
- 基於 esbuild 的 universal bundler 設計
- XCTFre逆向(四):insanity
- 亞線性的近似最小支撐樹
- JDBC編碼六步走
- 理解什麼是真正的並發數
- 143. 重排鏈錶
- JVM腦圖
- 【Pytorch(四)】學習如何使用 PyTorch 讀取並處理數據集
- 函數棧幀的創建與銷毀
- 構建神經網絡- 手寫字體識別案例
- 多模態生成模型ERNIE-VILG
- kotlin不容忽視的小細節
- 如何將PDF轉換成Word文檔?試試這款PDF轉Word工具—PDF to Word OCR
- 備戰一年,終於斬獲騰訊T3,我堅信成功是可以複制的