寫(xiě)在前面
由于本人實(shí)力尚淺，接觸算法沒(méi)多久，寫(xiě)這篇blog僅僅是想要提升自己對(duì)算法的理解，如果各位讀者發(fā)現(xiàn)什么錯(cuò)誤，懇請(qǐng)指正，希望和大家一起進(jìn)步。(●’?’●)
完全背包問(wèn)題
了解完全背包問(wèn)題前可以先去看看01背包問(wèn)題（良心正解），先了解這個(gè)基礎(chǔ)問(wèn)題會(huì)更有利于你了解下面的完全背包問(wèn)題（個(gè)人觀點(diǎn)）
題目
思路
重要變量說(shuō)明：
f[][[]:用于狀態(tài)表示；w[]：記錄每個(gè)物品的價(jià)值；v[]：記錄每個(gè)物品的體積
- 定義二維數(shù)組
f[][],其中f[i][j]表示在前i個(gè)物品，背包容積為j的限制下所能裝下的最大價(jià)值。這里的f[i][j]就是做法的集合，f[i][j]的值就是最大價(jià)值即屬性。 - 從
i=1開(kāi)始枚舉，對(duì)于第i個(gè)物品，都有無(wú)數(shù)種選擇（看似是無(wú)數(shù)種，其實(shí)還是有限制的）：- 如果不選第
i個(gè)物品，那么狀態(tài)轉(zhuǎn)移方程為f[i][j]=f[i-1][j] - 如果選擇第
i個(gè)物品一次，那么狀態(tài)轉(zhuǎn)移方程為f[i][j]=f[i-1][j-v[i]]+w[i] - 如果選擇第
i個(gè)物品二次，那么狀態(tài)轉(zhuǎn)移方程為f[i][j]=f[i-1][j-2*v[i]]+2*w[i] ......- 如果選擇第
i個(gè)物品k次，那么狀態(tài)轉(zhuǎn)移方程為f[i][j]=f[i-1][j-k*v[i]]+k*w[i]
- 如果不選第
- 我們因?yàn)橐笞畲髢r(jià)值，所以對(duì)上面兩種情況去
max即可
我們發(fā)現(xiàn)其實(shí)上面的思路大致上和01背包問(wèn)題差不多，只不過(guò)對(duì)于每一個(gè)物品
i，我們不止兩種選擇（選與不選）而是有無(wú)數(shù)種選擇。所以我們可以在01背包問(wèn)題的基礎(chǔ)上，在兩層循環(huán)中再套一層循環(huán)，表示選擇第i個(gè)物品多少次。
代碼（不優(yōu)化版，二維數(shù)組）
#include<iostream>
using namespace std;
const int N=1010;
int f[N][N],v[N],w[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++) //i表示當(dāng)前選擇到第i個(gè)物品，我們從第1個(gè)物品開(kāi)始枚舉，一直到n個(gè)物品
for(int j=1;j<=m;j++) //j表示當(dāng)前背包的容積，我們從1開(kāi)始枚舉，一直到背包的最大的容積
for(int k=0;k<=j/v[i];k++) //k表示當(dāng)前的選擇第i個(gè)物品的次數(shù)，一直到所能選擇的最大次數(shù)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
printf("%d\n",f[n][m]);
return 0;
}
優(yōu)化1（降低時(shí)間復(fù)雜度）
我們可以看到上面的思路雖然可以求解問(wèn)題，但是時(shí)間復(fù)雜度是 O ( l o g 2 n ) O(log_2n) O(log2?n)，而題目給出的數(shù)據(jù)是 1 0 3 10^3 103,那么最后就是 1 0 9 10^9 109，而我們的要求是1s內(nèi)，大概是 1 0 7 ? 1 0 8 10^7-10^8 107?108之間，所以我們還要優(yōu)化
思路
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上兩式，可得出如下遞推關(guān)系：
f[i][j]=max(f[i,j-v]+w , f[i-1][j])
還是沒(méi)看懂的寶寶們可以可以看下面這份詳細(xì)推理
代碼
#include<iostream>
using namespace std;
const int N=1010;
int f[N][N],v[N],w[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&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]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
else
f[i][j]=f[i-1][j];
}
printf("%d\n",f[n][m]);
return 0;
}
思考
我們把完全背包問(wèn)題和01背包問(wèn)題做一下對(duì)比：
01背包問(wèn)題：f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
完全背包問(wèn)題： f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);
于是乎，聰明的你一定想到了完全背包問(wèn)題的代碼還可以?xún)?yōu)化，只使用一維數(shù)組，降低空間復(fù)雜度
優(yōu)化2（降低空間復(fù)雜度）
具體為什么可以只用一維數(shù)組請(qǐng)看01背包問(wèn)題
代碼
#include<iostream>
using namespace std;
const int N=1010;
int f[N],v[N],w[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(j>=v[i])
f[j]=max(f[j],f[j-v[i]]+w[i]);
else
f[j]=f[j];
}
printf("%d\n",f[m]);
return 0;
}
再思考
Q：為什么01背包問(wèn)題使用一維數(shù)組時(shí)，枚舉背包空間時(shí)要逆序，而完全背包問(wèn)題使用一維數(shù)組時(shí)，枚舉背包空間時(shí)是正序？
A:01背包問(wèn)題中我們每次更新用的都應(yīng)該是上一層即i-1層的數(shù)據(jù)，但是如果正序枚舉背包空間j的話(huà)，在更新較大容積時(shí)，用到的就是已經(jīng)污染的數(shù)據(jù)，即在第i層時(shí)，可能在j=v[i]時(shí)選了i這個(gè)物品，當(dāng)j=2*v[i]時(shí)我們可能又選了i這個(gè)物品，而第i這個(gè)物品只能被選一次，而逆序枚舉時(shí)，每次都只可能選擇第i這個(gè)物品一次。但是在完全背包問(wèn)題中我們就要用正序，因?yàn)槲覀円木褪且呀?jīng)更新的數(shù)據(jù)，因?yàn)槊總€(gè)物品都有無(wú)數(shù)個(gè)，所以可以選擇第i個(gè)物品多次
如果你覺(jué)得我寫(xiě)題解還不錯(cuò)的，請(qǐng)各位王子公主移步到我的其他題解看看
數(shù)據(jù)結(jié)構(gòu)與算法部分（還在更新中）：
C++ STL總結(jié) - 基于算法競(jìng)賽（強(qiáng)力推薦）
最短路算法——Dijkstra（C++實(shí)現(xiàn)）
最短路算法———Bellman_Ford算法（C++實(shí)現(xiàn)）
最短路算法———SPFA算法（C++實(shí)現(xiàn)）
最小生成樹(shù)算法———prim算法（C++實(shí)現(xiàn)）
最小生成樹(shù)算法———Kruskal算法（C++實(shí)現(xiàn)）
染色法判斷二分圖（C++實(shí)現(xiàn)）
動(dòng)態(tài)規(guī)劃——01背包問(wèn)題
Linux部分（還在更新中）：
Linux學(xué)習(xí)之初識(shí)Linux
Linux學(xué)習(xí)之命令行基礎(chǔ)操作
???總結(jié)
“種一顆樹(shù)最好的是十年前,其次就是現(xiàn)在”
所以,
“讓我們一起努力吧,去奔赴更高更遠(yuǎn)的山?！?br>
如果有錯(cuò)誤?,歡迎指正喲??文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-762112.html
??如果覺(jué)得收獲滿(mǎn)滿(mǎn),可以動(dòng)動(dòng)小手,點(diǎn)點(diǎn)贊??,支持一下喲??文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-762112.html
到了這里，關(guān)于動(dòng)態(tài)規(guī)劃——完全背包問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
