您好,登錄后才能下訂單哦!
這篇文章主要介紹了C語(yǔ)言動(dòng)態(tài)規(guī)劃多種背包問(wèn)題怎么解決的相關(guān)知識(shí),內(nèi)容詳細(xì)易懂,操作簡(jiǎn)單快捷,具有一定借鑒價(jià)值,相信大家閱讀完這篇C語(yǔ)言動(dòng)態(tài)規(guī)劃多種背包問(wèn)題怎么解決文章都會(huì)有所收獲,下面我們一起來(lái)看看吧。
C語(yǔ)言數(shù)學(xué)問(wèn)題與簡(jiǎn)單DP01背包問(wèn)題詳解
先回憶一下這個(gè)圖
在這我再將01背包問(wèn)題代碼發(fā)一遍,可以用來(lái)做對(duì)比。
二維:
#include<bits/stdc++.h> using namespace std; const int MAXN = 1005; int v[MAXN]; // 體積 int w[MAXN]; // 價(jià)值 int f[MAXN][MAXN]; // f[i][j], j體積下前i個(gè)物品的最大價(jià)值 int main() { int n, m; 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++) { // 當(dāng)前背包容量裝不進(jìn)第i個(gè)物品,則價(jià)值等于前i-1個(gè)物品 if(j < v[i]) f[i][j] = f[i - 1][j]; // 能裝,需進(jìn)行決策是否選擇第i個(gè)物品 else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]); } cout << f[n][m] << endl; return 0; }
一維:
#include<bits/stdc++.h> using namespace std; const int MAXN = 1005; int f[MAXN]; // int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { int v, w; cin >> v >> w; // 邊輸入邊處理 for(int j = m; j >= v; j--) f[j] = max(f[j], f[j - v] + w); } cout << f[m] << endl; return 0; }
完全背包問(wèn)題和01背包問(wèn)題的區(qū)別就在于完全背包問(wèn)題中每件物品都有無(wú)限件可用。我們也可以先來(lái)試一下暴力寫(xiě)法。
#include<iostream> using namespace std; const int N = 1010; int n, m; int dp[N][N], v[N], w[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 = 0; j <= m; j ++ ) for(int k = 0; k * v[i] <= j; k ++ )//因?yàn)槊恳患锲范加袩o(wú)限件可用,我們只需要找出單件價(jià)值最高的商品就可以了 dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]); cout << dp[n][m] << endl; }
優(yōu)化思路:
我們列舉一下更新次序的內(nèi)部關(guān)系:
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , …)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-3v]+2*w , …)
由上兩式,可得出如下遞推關(guān)系:
f[i][j]=max(f[i,j-v]+w , f[i-1][j])
有了上面的關(guān)系,那么其實(shí)k循環(huán)可以不要了,核心代碼優(yōu)化成這樣:
for(int i = 1 ; i <=n ;i++) for(int j = 0 ; j <=m ;j++) { f[i][j] = f[i-1][j]; if(j-v[i]>=0) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]); }
這個(gè)代碼和01背包的非優(yōu)化寫(xiě)法很像啊!!!我們對(duì)比一下,下面是01背包的核心代碼
for(int i = 1 ; i <= n ; i++) for(int j = 0 ; j <= m ; j ++) { f[i][j] = f[i-1][j]; if(j-v[i]>=0) f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]); }
兩個(gè)代碼其實(shí)只有一句不同(注意下標(biāo))
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包
f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包問(wèn)題
因?yàn)楹?1背包代碼很相像,我們很容易想到進(jìn)一步優(yōu)化。核心代碼可以改成下面這樣
for(int i = 1 ; i<=n ;i++) for(int j = v[i] ; j<=m ;j++)//注意了,這里的j是從小到大枚舉,和01背包不一樣 { f[j] = max(f[j],f[j-v[i]]+w[i]); }
綜上所述,完全背包的最終寫(xiě)法如下:
#include<iostream> using namespace std; const int N = 1010; int f[N]; int v[N],w[N]; int main() { int n,m; 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 = v[i] ; j<=m ;j++) { f[j] = max(f[j],f[j-v[i]]+w[i]); } cout<<f[m]<<endl; }
我們先來(lái)看這多重背包問(wèn)題和01背包問(wèn)題是不是很像,將s×v,s×w是不是就可以看成01背包問(wèn)題了?
for(ll i=1;i<=n;i++) { cin>>a>>b>>c; for(ll j=1;j<=c;j++) { v[cnt]=a; w[cnt]=b; cnt++; }//將多重背包一個(gè)一個(gè)拆出來(lái) }
然后轉(zhuǎn)換成01背包問(wèn)題解決。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=1e5+100; ll v[N],w[N]; ll f[N]; int main() { ll n,m; ll cnt=1; cin>>n>>m; ll a,b,c; for(ll i=1;i<=n;i++) { cin>>a>>b>>c; for(ll j=1;j<=c;j++) { v[cnt]=a; w[cnt]=b; cnt++; }//將多重背包一個(gè)一個(gè)拆出來(lái) } for(ll i=1;i<=cnt;i++) { for(ll j=m;j>=v[i];j--) { f[j]=max(f[j],f[j-v[i]]+w[i]); } }//01背包 cout<<f[m]; return 0; }
這道題和1看起來(lái)沒(méi)什么區(qū)別,但是數(shù)據(jù)范圍變了,數(shù)據(jù)范圍變了如果不優(yōu)化就話(huà)超時(shí),那怎么優(yōu)化呢?
我們只需要將轉(zhuǎn)換成01背包問(wèn)題那一部分優(yōu)化了就可以了。
int cnt = 0; // 將物品重新分組后的順序 for (int i = 1; i <= n; i ++) { int a, b, s; // a 體積, b 價(jià)值, s 每種物品的個(gè)數(shù) scanf("%d %d %d", &a, &b, &s); int k = 1; // 二進(jìn)制拆分 打包時(shí)每組中有 k 個(gè)同種物品 while (k <= s) // 即y總說(shuō)的: 最后一組的物品個(gè)數(shù) < 2^(n+1) 1 2 4 8 16 ... 2^n 2^(n+1) { cnt ++; v[cnt] = a * k; // 每組的體積 w[cnt] = b * k; // 每組的價(jià)值 s -= k; k *= 2; // 注意是 k * 2,每次增長(zhǎng)一倍,不是k * k } if (s > 0) // 二進(jìn)制拆分完之后 剩下的物品個(gè)數(shù)分為新的一組 { cnt ++; v[cnt] = a * s; w[cnt] = b * s; } }
我們知道任何一個(gè)數(shù)都可以轉(zhuǎn)化成二進(jìn)制的數(shù),那二進(jìn)制和十進(jìn)制的區(qū)別在哪呢?
普通遍歷問(wèn)題
遍歷 n 個(gè)物品, 采用二進(jìn)制計(jì)數(shù)方法遍歷與采用十進(jìn)制技術(shù)方法遍歷的時(shí)間復(fù)雜度是一樣的
舉例來(lái)說(shuō), 對(duì)于十進(jìn)制數(shù) 8
十進(jìn)制遍歷: 0,1,2,3,4,5,6,7 共 8 次遍歷
二進(jìn)制遍歷: 000, 001, 010, 011, 100, 101, 110, 111 共 8 次遍歷
多重背包問(wèn)題
同樣的道理, 對(duì)于多重背包問(wèn)題, 采用二進(jìn)制的遍歷方法不能優(yōu)化時(shí)間復(fù)雜度
優(yōu)化的原因在于引入了動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度 ≈≈ 問(wèn)題的總個(gè)數(shù) × 問(wèn)題要做出的選擇數(shù)
如, 對(duì)于 01 背包問(wèn)題, 問(wèn)題的總個(gè)數(shù)為N⋅V (N 為物品個(gè)數(shù), V 為背包容量), 問(wèn)題要做出的選擇數(shù)為 2(選或不選)
則 01 背包問(wèn)題的時(shí)間復(fù)雜度約為 2N⋅V
如果不采用動(dòng)態(tài)規(guī)劃的做法, 就像普通的遍歷問(wèn)題那樣, 是否采用二進(jìn)制的計(jì)數(shù)方法對(duì)時(shí)間復(fù)雜度的優(yōu)化沒(méi)有任何關(guān)系
但采用二進(jìn)制的計(jì)數(shù)方法會(huì)影響問(wèn)題的總個(gè)數(shù)與問(wèn)題的選擇數(shù)的乘積, 即動(dòng)態(tài)規(guī)劃做法下多重背包的時(shí)間復(fù)雜度
多重背包的動(dòng)態(tài)規(guī)劃時(shí)間復(fù)雜度
十進(jìn)制遍歷方法
問(wèn)題的總個(gè)數(shù)為 N⋅V, N 為物品的種類(lèi)數(shù), V 為背包容量
問(wèn)題的選擇數(shù)約為 Smax,Smax 為每種物品數(shù)量的最大值
十進(jìn)制下多重背包問(wèn)題的 DP 時(shí)間復(fù)雜度為: N⋅V⋅Smax
二進(jìn)制遍歷方法
十進(jìn)制下, 一種物品有 si個(gè), 二進(jìn)制下, 變?yōu)?1, 2, … , lgsi 個(gè)物品, 則共有 lgs1+lgs2+…+lg?sn 個(gè)物品, 約為 Nlgsmax 個(gè)物品
問(wèn)題的總個(gè)數(shù)為 N⋅V⋅lgsmax
問(wèn)題的選擇數(shù)為 2
十進(jìn)制下多重背包問(wèn)題的 DP 時(shí)間復(fù)雜度為: 2N⋅V⋅lgsmax
最后請(qǐng)看代碼
#include <bits/stdc++.h> using namespace std; const int N = 11 * 1000 + 10, M = 2010; int v[N], w[N]; int f[M]; int main() { int n, m; scanf("%d %d", &n, &m); int cnt = 0; // 將物品重新分組后的順序 for (int i = 1; i <= n; i ++) { int a, b, s; // a 體積, b 價(jià)值, s 每種物品的個(gè)數(shù) scanf("%d %d %d", &a, &b, &s); int k = 1; // 二進(jìn)制拆分 打包時(shí)每組中有 k 個(gè)同種物品 while (k <= s) // 即y總說(shuō)的: 最后一組的物品個(gè)數(shù) < 2^(n+1) 1 2 4 8 16 ... 2^n 2^(n+1) { cnt ++; v[cnt] = a * k; // 每組的體積 w[cnt] = b * k; // 每組的價(jià)值 s -= k; k *= 2; // 注意是 k * 2,每次增長(zhǎng)一倍,不是k * k } if (s > 0) // 二進(jìn)制拆分完之后 剩下的物品個(gè)數(shù)分為新的一組 { cnt ++; v[cnt] = a * s; w[cnt] = b * s; } } n = cnt; // 所有的組數(shù)即為 01背包中的物品個(gè)數(shù) // 寫(xiě)01背包模板 for (int i = 1; i <= n; i ++) for (int j = m; j >= v[i]; j --) f[j] = max(f[j], f[j - v[i]] + w[i]); printf("%d", f[m]); return 0; }
狀態(tài)表示:f[i][j]
集合:從前i組物品中選,且總體積不超過(guò)j的所有方案的集合.
屬性:最大值
狀態(tài)計(jì)算:
思想-----集合的劃分
集合劃分依據(jù):根據(jù)從第i組物品中選哪個(gè)物品進(jìn)行劃分.
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
請(qǐng)看代碼
#include<bits/stdc++.h> using namespace std; const int N=110; int f[N][N]; //只從前i組物品中選,當(dāng)前體積小于等于j的最大值 int v[N][N],w[N][N],s[N]; //v為體積,w為價(jià)值,s代表第i組物品的個(gè)數(shù) int n,m,k; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>s[i]; for(int j=0;j<s[i];j++){ cin>>v[i][j]>>w[i][j]; //讀入 } } for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ f[i][j]=f[i-1][j]; //不選 不選表示不選第 i 組物品的所有物品,只從前 i?1 組物品里面選 for(int k=0;k<s[i];k++){ if(j>=v[i][k]) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]); } } } cout<<f[n][m]<<endl; }
因?yàn)橹挥玫搅说趇-1列,所以可以仿照01背包的套路逆向枚舉體積
#include<bits/stdc++.h> using namespace std; const int N=110; int f[N]; int v[N][N],w[N][N],s[N]; int n,m,k; int main(){ cin>>n>>m; for(int i=0;i<n;i++){ cin>>s[i]; for(int j=0;j<s[i];j++){ cin>>v[i][j]>>w[i][j]; } } for(int i=0;i<n;i++){ for(int j=m;j>=0;j--){ for(int k=0;k<s[i];k++){ //for(int k=s[i];k>=1;k--)也可以 if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); } } } cout<<f[m]<<endl; }
關(guān)于“C語(yǔ)言動(dòng)態(tài)規(guī)劃多種背包問(wèn)題怎么解決”這篇文章的內(nèi)容就介紹到這里,感謝各位的閱讀!相信大家對(duì)“C語(yǔ)言動(dòng)態(tài)規(guī)劃多種背包問(wèn)題怎么解決”知識(shí)都有一定的了解,大家如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。