?博主：命運之光??????
??專欄：算法修煉之練氣篇?????
??專欄：算法修煉之筑基篇
?博主的其他文章：點擊進(jìn)入博主的主頁??????
前言：學(xué)習(xí)了算法修煉之練氣篇想必各位蒟蒻們的基礎(chǔ)已經(jīng)非常的扎實了，下來我們進(jìn)階到算法修煉之筑基篇的學(xué)習(xí)。筑基期和練氣期難度可謂是天差地別，懂得都懂，題目難度相比起練氣期的題目難度提升很多，所以要是各位蒟蒻小伙伴們看不懂筑基期的題目可以在練氣期多積累積累，練氣期的題目也會不斷更新，大家一定要把基礎(chǔ)打牢固了再來看筑基期的題目哈，這樣子也可以提高大家的學(xué)習(xí)效率，一舉兩得，加油(●'?'●)????
目錄
?詳解文字版（01背包，完全背包，多重背包）
??01背包問題
???完全背包問題
??多重背包問題
?01背包問題（經(jīng)典）
??小明的背包1
??解法一：二維dp數(shù)組
??解法二：一維dp數(shù)組
?完全背包問題（經(jīng)典）
??小明的背包2
??一維dp數(shù)組
??一維dp數(shù)組關(guān)鍵步驟（記憶）
??01背包和完全背包兩個對比（重要）
??總結(jié)就一個公式（超級無敵重要）
????01背包總結(jié)
????完全背包總結(jié)
?多重背包問題（經(jīng)典）
??小明的背包3
??重要步驟
?詳解文字版（01背包，完全背包，多重背包）
光看文字我感覺，很難理解背包問題，關(guān)鍵還是要看看底下的經(jīng)典例題，看完差不多就可以了，問題不好理解，大家加油哈(●'?'●)
背包問題的理解和解法。這三種問題分別是：
- 01背包問題：每種物品只能選擇一次，求最大價值。
- 完全背包問題：每種物品可以選擇無限次，求最大價值。
- 多重背包問題：每種物品有一個選擇上限，求最大價值。
這三種問題都可以用動態(tài)規(guī)劃的思想來解決，關(guān)鍵是找到狀態(tài)轉(zhuǎn)移方程。下面我就分別介紹一下這三種問題的思路和代碼實現(xiàn)。（看不懂的話可以直接跳到例題，看例題我感覺就能直接理解，不用文字這么的啰嗦哈哈啊哈??）
??01背包問題
01背包問題是所有背包問題的基礎(chǔ)，之后的問題都可以在此基礎(chǔ)之上變化，所以一定要理解清楚。尤其是對待不同問題，找出狀態(tài)轉(zhuǎn)移方程是解題的關(guān)鍵。
假設(shè)有N件物品和一個容量為V的背包。第i件物品的體積是v[i]，價值是w[i]。我們用f[i][j]表示前i件物品恰好放入一個容量為j的背包中的最大價值。那么我們可以得到如下的狀態(tài)轉(zhuǎn)移方程：
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])
這個方程的意思是，對于第i件物品，我們有兩種選擇：放或者不放。如果不放，那么前i件物品的最大價值就等于前i-1件物品的最大價值；如果放，那么前i件物品的最大價值就等于前i-1件物品在剩余空間j-v[i]中的最大價值加上第i件物品的價值。我們?nèi)∵@兩種情況中較大的一個作為f[i][j]的值。
根據(jù)這個方程，我們可以用二維數(shù)組來存儲f[i][j]的值，并從小到大遍歷所有可能的狀態(tài)。最終答案就是f[N][V]。
??下面是用C++實現(xiàn)的代碼：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1001; // 物品數(shù)量和背包容量的上限
int f[N][N]; // 存儲狀態(tài)轉(zhuǎn)移方程的結(jié)果
int v[N]; // 存儲每件物品的體積
int w[N]; // 存儲每件物品的價值
int main() {
int n, V; // 物品數(shù)量和背包容量
cin >> n >> V;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i]; // 輸入每件物品的體積和價值
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
f[i][j] = f[i-1][j]; // 不放第i件物品
if (j >= v[i]) { // 如果能放得下第i件物品
f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]); // 取放和不放中較大的一個
}
}
}
cout << f[n][V] << endl; // 輸出最大價值
return 0;
}???完全背包問題
完全背包問題與01背包問題非常相似，只是每種物品可以選擇無限次而已。這樣一來，我們的狀態(tài)轉(zhuǎn)移方程就有所變化：
f[i][j] = max(f[i-1][j], f[i][j-v[i]] + w[i])
這個方程的意思是，對于第i件物品，我們有兩種選擇：放或者不放。如果不放，那么前i件物品的最大價值就等于前i-1件物品的最大價值；如果放，那么前i件物品的最大價值就等于當(dāng)前物品在剩余空間j-v[i]中的最大價值加上第i件物品的價值。注意這里和01背包問題的區(qū)別，因為可以放多次，所以是f[i][j-v[i]]而不是f[i-1][j-v[i]]。
根據(jù)這個方程，我們?nèi)匀豢梢杂枚S數(shù)組來存儲f[i][j]的值，并從小到大遍歷所有可能的狀態(tài)。最終答案仍然是f[N][V]。
??下面是用C++實現(xiàn)的代碼：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1001; // 物品數(shù)量和背包容量的上限
int f[N][N]; // 存儲狀態(tài)轉(zhuǎn)移方程的結(jié)果
int v[N]; // 存儲每件物品的體積
int w[N]; // 存儲每件物品的價值
int main() {
int n, V; // 物品數(shù)量和背包容量
cin >> n >> V;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i]; // 輸入每件物品的體積和價值
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
f[i][j] = f[i-1][j]; // 不放第i件物品
if (j >= v[i]) { // 如果能放得下第i件物品
f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]); // 取放和不放中較大的一個
}
}
}
cout << f[n][V] << endl; // 輸出最大價值
return 0;
}??多重背包問題
多重背包問題的描述是這樣的：有n種物品和一個容量為m的背包，每種物品有一定的重量w[i]和價值v[i]，還有數(shù)量限制num[i]，即每種物品最多只能放num[i]個。問如何選擇放入背包的物品，使得背包內(nèi)物品的總價值最大，且不超過背包的容量。??
這個問題看起來很復(fù)雜，但其實我們可以用一些技巧來簡化它。首先，我們可以把每種物品看成是若干個01背包問題中的物品，即把第i種物品分成num[i]個單獨的物品，每個物品的重量和價值都是w[i]和v[i]。這樣我們就把多重背包問題轉(zhuǎn)化成了一個01背包問題。??
然后，我們可以用一個二維數(shù)組dp[i][j]來表示從前i個物品中選擇若干個放入容量為j的背包時能獲得的最大價值。我們可以用一個循環(huán)來遍歷所有的物品，對于每個物品，我們又用一個循環(huán)來遍歷所有可能的背包容量，然后根據(jù)放或不放這個物品來更新dp[i][j]的值。具體來說，如果不放這個物品，那么dp[i][j]就等于dp[i-1][j]，即前i-1個物品放入容量為j的背包時能獲得的最大價值；如果放這個物品，那么dp[i][j]就等于dp[i-1][j-w[i]]+v[i]，即前i-1個物品放入容量為j-w[i]的背包時能獲得的最大價值加上當(dāng)前物品的價值。我們要在這兩種情況中取較大的那個作為dp[i][j]的值。??
最后，我們可以輸出dp[n][m]作為最終答案，即從n種物品中選擇若干個放入容量為m的背包時能獲得的最大價值。這就是多重背包問題的解法。??
?01背包問題（經(jīng)典）
??小明的背包1
??解法一：二維dp數(shù)組
#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005],w[1005],v[1005];
int main()
{
//經(jīng)典的01背包問題需要記憶
int n,m;
int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(j<w[i])
{
dp[i][j]=dp[i-1][j];//記憶
}
else
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//記憶
}
}
}
cout<<dp[n][m];
return 0;
}??解法二：一維dp數(shù)組
#include<bits/stdc++.h>
using namespace std;
int dp[1005],w[1005],v[1005];
int main()
{
//經(jīng)典的01背包問題需要記憶
int n,m;
int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
for(i=1;i<=n;i++)
{
for(j=m;j>=1;j--)//--j和j--不影響，01背包是逆序
{
if(j>w[i])
{
dp[j]=max(dp[j-1],dp[j-w[i]]+v[i]);
}
}
}
cout<<dp[m];
return 0;
}??用這個dp[j]=max(dp[j],dp[j-w[i]]+v[i])
#include<bits/stdc++.h>
using namespace std;
int dp[1005],w[1005],v[1005];
int main()
{
//經(jīng)典的01背包問題需要記憶
int n,m;
int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
for(i=1;i<=n;i++)
{
for(j=m;j>=1;j--)//--j和j--不影響，01背包是逆序
{
if(j>=w[i])
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m];
return 0;
}下面是需要記憶知識點（01背包問題中的推到公式需要記憶）
??二維dp數(shù)組
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(j<w[i])
{
dp[i][j]=dp[i-1][j];//記憶
}
else
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//記憶
}
}
}??一維dp數(shù)組（重要）
for(i=1;i<=n;i++)
{
for(j=m;j>=1;j--)//--j和j--不影響，01背包是逆序
{
if(j>=w[i])
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
} 
?完全背包問題（經(jīng)典）
??小明的背包2
??一維dp數(shù)組
#include<bits/stdc++.h>
using namespace std;
int dp[1005],w[1005],v[1005];
int main()
{
//經(jīng)典的完全背包問題需要記憶
int n,m;
int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
for(i=1;i<=n;i++)
{
for(j=w[i];j<=m;j++)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m];
return 0;
}??一維dp數(shù)組關(guān)鍵步驟（記憶）
for(i=1;i<=n;i++)
{
for(j=w[i];j<=m;j++)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
} 
??01背包和完全背包兩個對比（重要）
??總結(jié)就一個公式（超級無敵重要）
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
其中01背包是逆向推到，完全背包是正向推到
????01背包總結(jié)
for(i=1;i<=n;i++)
{
for(j=m;j>=1;j--)//--j和j--不影響，01背包是逆序
{
if(j>=w[i])
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
} ????完全背包總結(jié)
for(i=1;i<=n;i++)
{
for(j=w[i];j<=m;j++)//重要點，j=w[i];j<=m;j++
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
} ?多重背包問題（經(jīng)典）
理解了上面的01背包問題和多重背包問題就很好理解多重背包問題了
??小明的背包3
文章來源：http://www.zghlxwxcb.cn/news/detail-478089.html
#include<bits/stdc++.h>
using namespace std;
int dp[205],w[205],vi[205],s[205];
int main()
{
//經(jīng)典的多重背包問題
int n,v;
int i,j;
cin>>n>>v;
for(i=1;i<=n;i++)
{
cin>>w[i]>>vi[i]>>s[i];
}
for(i=1;i<=n;i++)
{
for(j=v;j>=1;j--)
{
for(int k=0;k<=s[i]&&j>=k*w[i];++k)
{
//從01背包的狀態(tài)轉(zhuǎn)移方程式，去增加i個物品拿k個循環(huán)
dp[j]=max(dp[j],dp[j-k*w[i]]+k*vi[i]);
}
}
}
cout<<dp[v];
return 0;
}??重要步驟
??就是在01背包的基礎(chǔ)上加上K循環(huán)的約束條件和dp[j]=max(dp[j],dp[j-k*w[i]]+k*vi[i])文章來源地址http://www.zghlxwxcb.cn/news/detail-478089.html
for(i=1;i<=n;i++)
{
for(j=v;j>=1;j--)//01背包的基礎(chǔ)上他這個也是逆向的
{
for(int k=0;k<=s[i]&&j>=k*w[i];++k)
{
//從01背包的狀態(tài)轉(zhuǎn)移方程式，去增加i個物品拿k個循環(huán)
dp[j]=max(dp[j],dp[j-k*w[i]]+k*vi[i]);
}
}
}到了這里，關(guān)于算法修煉之筑基篇——筑基一層中期（解決01背包，完全背包，多重背包）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
