當前位置:網站首頁>動態規劃背包問題之完全背包詳解
動態規劃背包問題之完全背包詳解
2022-07-23 16:30:51【四舍五入兩米高的小晨】
上一篇我們學習了什麼是動態規劃問題和什麼是背包問題,並且分析了01背包,如果想看上一篇請轉移至–>背包問題之01背包詳解,今天我們來了解一下背包問題之完全背包問題.
文章目錄
一、什麼是完全背包問題?
有n種物品,每種物品的單件體積為v[i],價值為w[i]。現有一個容量為V的背包,問如何選取物品放入背包,使得背包內物品的總價值最大。其中每種物品都有無窮件。
完全背包和01背包的區別:
- 01背包在選擇某一個物品時只有不選和選一次兩種情况
- 完全背包在選擇某一個物品時可以不選,也可以選一次,選兩次。。。選擇次數沒有上限(只要背包能放下)
二、例題分析
1. 題目:
2. 分析:
2.1 第一步:確定狀態變量(函數)
最大價值是物品數量i和背包容量j的函數。
設函數f[i][j]錶示前i件物品放入容量為j的背包的最大價值。
最終的最大價值就是物品數量i從0增長到n,背包容量j從0增長到m時的f[n][m]值。
2.2 第二步:確定狀態轉移方程
狀態變量:f[i][j]錶示前i件物品放入容量為j的背包的最大價值
當前容量為j,我們要考慮第i件物品能否放入?是否放入?
- 如果當前背包容量j<v[i],不能放入,則f[i][j]=f[i-1][j]
- 如果當前背包容量j>=v[i],能放入但是要比較代價
2.1 如果第i件物品不放入背包,則f[i][j]=f[i-1][j]
2.2 如果第i件物品放入背包,則f[i][j]=f[i][j-v[i]]+w[i]
對於前i件物品,背包容量為j-v[i]時可能已經放入了第i件物品,容量為j時還可以再放入第i件物品,所以用f[i][j-v[i]]更新f[i][j]
狀態轉移方程:
可以畫圖錶示為:
2.3 邊界條件
對於01背包來說邊界就是f[i][j]=0,即當i=0或者j=0時f[i][j]的值為0。
i=0時,錶示背包沒有放入一個物品,那麼此時背包的最大價值無從談起,所以為0;
j=0時,錶示背包的容量為0,那麼此時無法放入物品,所以最大價值也為0;
3. 過程錶示
3.1 核心代碼
for(int i=1;i<=n;i++){
//物品i
for(int j=0;j<=m;j++)
{
if(j<v[i])
f[i][j]=f[i-1][j];
else
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<endl;
3.2 手動計算
3.3 代碼驗證
3.4 完整代碼
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main ()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(j<v[i])
f[i][j]=f[i-1][j];
else
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
}
cout<<f[n][m]<<endl;
return 0;
}
3.5 優化
將二維錶示優化成一維,减少空間的使用,用一維數組f[j]只記錄一行數據,讓j值順序循環,順序更新f[j]
優化後的代碼
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main ()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(j<v[i])
f[j]=f[j];
else
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
cout<<f[m]<<endl;
return 0;
}
因為j是順序循環,f[j-v[i]]會先於f[j]更新,也就是說,用新值f[j-v[i]]去更新f[j],相當於用第i行的f[j-v[i]]值更新f[j],所以正確。
版權聲明
本文為[四舍五入兩米高的小晨]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/204/202207231229588777.html
邊欄推薦
猜你喜歡
隨機推薦
- BGP機房的優點
- 真人踩過的坑,告訴你避免自動化測試常犯的10個錯誤
- 判斷是否為void類型
- C語言——幾道C語言經典習題
- openvino_datawhale
- C語言基礎知識梳理(一)
- Redis源碼與設計剖析 -- 7.快速列錶
- 比特,比特,字節,字的概念與區別
- 項目部署(簡版)
- JDBC的學習以及簡單封裝
- [pytho-flask筆記5]藍圖簡單使用
- Web Component-自定義元素的生命周期
- 數倉4.0筆記——業務數據采集
- 數倉4.0筆記——用戶行為數據采集四
- 對.h5文件的迭代顯示,h5py數據操作
- 常用數學知識匯總
- “東數西算”下數據中心的液冷GPU服務器如何發展?
- 硬件知識1--原理圖和接口類型(基於百問網硬件操作大全視頻教程)
- 鋼結構基本原理複習
- Unity3d:UGUI源碼,Rebuild優化
- 快速解决:Xshell拖不進去文件夾或者軟件包的問題
- RHCSA--文件內容瀏覽、cut、uniq、sort、.tr命令使用
- 信號完整性(SI)電源完整性(PI)學習筆記(三十二)電源分配網路(四)
- EasyGBS平臺出現錄像無法播放並存在RTMP重複推流現象,是什麼原因?
- 第七天筆記
- 【可視化調度軟件】上海道寧為SMB組織帶來NETRONIC下載、試用、教程
- 概率沉思錄:2.The quantitative rules
- 常用的鼠標事件和鍵盤事件
- C#:in、out、ref關鍵字
- GRE,MGRE的詳細了解;OSPF基礎配置知識
- Creo 9.0 如何快速修改CAD坐標系?
- 第五天筆記
- 强化學習——策略梯度理解點
- shell跑的時候需要的需要了解命令
- OKRK3399開發板預留I2C4掛載EEPROM
- 優化華為雲服務器采用Key登陸
- 第2章 基礎查詢與排序
- 【C語言】猜數字小遊戲+關機小程序
- 什麼是Per-Title編碼?
- @FeignClient使用詳細教程(圖解)