我們知道，背包問題是一種非常經典的動態規劃問題，本文總結了幾種類型的背包問題並進行了分析：
根據百度百科，我們可以看到背包問題(Knapsack problem)是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中。相似問題經常出現在商業、組合數學，計算複雜性理論、密碼學和應用數學等領域中。也可以將背包問題描述為决定性問題，即在總重量不超過W的前提下，總價值是否能達到V？它是在1978年由Merkle和Hellman提出的。
一般來講，我們可以將其分為一下幾種類型：
·01背包問題
·完全背包問題
·多重背包問題
·組合背包問題
我們就一個一個的來解决，第一個我們先看到最基礎的01背包問題：
01背包就是告訴我們有n件物品，每件物品你要麼選要麼不選，最多選一次；
我們先考慮一下樸素算法，也就是暴力窮舉的方法，但是發現很明顯這樣有2^n種可能性，這是不可接受的 。 而我們這裏如果是用動態規劃的話可以有效的將時間複雜度降低到O（NV），這裏我們就要把問題空間中的目標和狀態給提取出來，所以我們定義狀態為：
dp[i][j]錶示只有前i件物品考慮放進去或者不放進去，總體積不超過j時，所能達到的最大價值。
我們先把所有的dp初始化為0，然後我們考慮要不要裝入第i件物品，有以下兩種可能：
1.不裝入第i件物品，則dp[i][j] = dp[i-1][j];
2.裝入第i件物品的情况下，dp[i][j] = dp[i-1][j - v[i] ] + w[i];
這是dp[i][j]的在考察到第i件物品時的兩種 可能，所以我們可以得出狀態轉移方程如下：
dp[i][j] = max(dp[i-1][j] , dp[i-1][j - v[i] ] + w[i] );
而且，我們可以發現，dp[i][j]至於dp[i-1][0~j-1]有關，所以我們可以使用動態規劃十分常用的空間優化（滾動數組，即去掉dp的第一維），然後在第i層下，如果dp[j]未被更新過，就是dp[i-1][j]，如果被更新過了就是dp[i][j]了，所以我們可以發現進行空間優化之後，我們不能覆蓋上一層的循環，所以枚舉體積j的時候只能逆向枚舉，這是為了避免拿更新過的數值繼續更新同一維的數值；
這裏體現了動態規劃的核心思想就是避免重複計算，第i件物品裝入與不裝入而獲得的最大價值完全可以由前i-1件物品的最大價值决定，而暴力枚舉忽略了這個事實！
代碼：
#include<bits/stdc++.h>
#define maxn 1010
using namespace std;
int v[maxn],w[maxn];
int f[maxn];
int n,m;
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 = m;j>=v[i];j--)
f[j] = max(f[j - v[i]] + w[i], f[j]);
cout << f[m] << '\n';
return 0;
}
接下來，我們接著考慮第二種背包問題也就是完全背包問題：
完全背包問題和上面的01背包問題不一樣的是，完全背包問題中第i件物品有無窮的後備，可以想拿多少拿多少；
我們有常見的兩種分析思路，首先我們可以和01背包問題一樣先定義一下狀態：
dp[i][j]錶示只有前i件物品考慮放進去或者不放進去，總體積不超過j時，所能達到的最大價值。
但是我們在這裏考慮第i件物品要不要加一個進去 的時候，我們不用考慮dp[i-1][j - v[i] ] , 而是轉移到dp[i][j - v[i] ]中，也就是說在加入了第i件商品之後是否還可以加入第i件商品；
我們也可以寫成：
dp[i][j] = max(dp[i-1][j] , dp[i-1][j - v[i] ] + w[i] , dp[i-1][j - 2*v[i] ] + 2*w[i] ……，dp[i-1][j - k*v[i] ] + k*w[i] )
dp[i][j - v[i] ] = max(dp[i-1][j - v[i] ] , dp[i-1][j - 2*v[i] ] + w[i] ……，dp[i-1][j - k*v[i] ] + (k-1)*w[i] )
我們可以發現上面紅色的部分只差了w[i]，所以我們可以將狀態轉移方程寫為：
dp[i][j] = min(dp[i][j - v[i] ] + w[i] , dp[i-1][j]);
這是第一種分析方式，接下來是第二種分析方式，就是直接把上面的k一個個列出來取最值，比較麻煩，所以這裏不贅述了！
代碼：
#include<bits/stdc++.h>
#define maxn 1010
using namespace std;
int v[maxn],w[maxn];
int f[maxn];
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] << '\n';
return 0;
}
這裏同樣可以進行空間優化，是同樣的方法，但是我們發現因為我們狀態轉移方程的時候，用到了dp[i][j - v[i] ],所以說我們可以用更新後的數值去更新同一維的數值，所以這裏我們不需要進行逆向窮舉可以直接進行正向循環枚舉；
接下來的而這個問題稱為多重背包問題，是因為這裏的第i件物品既不像01背包物品中那樣限定最多選一件，也沒有像完全背包問題中那樣可以選無限多件，也是可以根據數據的複雜程度，我們分為兩種分析方式：
·················未完待續···············
