1、背包問題

1.1、01背包

題目：

有n件物品和一個(gè)容量為m的背包，第i件物品的體積是v[ i ]，價(jià)值是w[ i ]，每件物品只有一件，求在不超過背包容量的前提下，可以放的物品的最大價(jià)值是多少

基本思路：

每個(gè)物品只有一件，考慮去或者不取

狀態(tài)設(shè)計(jì)：

//二維
狀態(tài)表示：f[i][j]集合：從前i個(gè)物品中選，總體積不超過j的物品的價(jià)值屬性：max
狀態(tài)計(jì)算：選第i個(gè)物品：f[i][j]=min(f[i-1][j-v[i]]+w[i],f[i][j]);不選第i個(gè)物品：f[i][j]=min(f[i-1][j],f[i][j]);//時(shí)間復(fù)雜度基本無法優(yōu)化，空間復(fù)雜度可以優(yōu)化
//一維：由于每一次狀態(tài)計(jì)算時(shí)僅需考慮計(jì)算上一個(gè)物品后的狀態(tài)，但需要從m~0枚舉體積
狀態(tài)計(jì)算：f[j]=max(f[j],f[j-v[i]]+w[i]);

代碼：

//不優(yōu)化：二維
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N=1100;
int f[N][N];
int w[N],v[N];
int n,m;
int res;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++){f[i][j]=f[i-1][j];if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);}}for(int i=1;i<=m;i++)   res=max(f[n][i],res);cout<<res;return 0;
}
//優(yōu)化·一維
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 1111;
int f[N];
int n,m;
int 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=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];return 0;
}

1.2、完全背包

題目：

有n件物品和一個(gè)容量為m的背包，第i件物品的體積是v[ i ]，價(jià)值是w[ i ]，每件物品有無限多件，求在不超過背包容量的前提下，可以放的物品的最大價(jià)值是多少

基本思路：

由于每種物品有無限多件，所以對(duì)于每種物品有無限多種選擇（選0個(gè)，選1個(gè)······選n個(gè)）

狀態(tài)設(shè)計(jì)：

狀態(tài)表示：f[i][j]集合：從前i個(gè)物品中選，總體積不超過j的物品的價(jià)值屬性：max
狀態(tài)計(jì)算：//樸素O(n^3)：枚舉每件物品取多少件(k:0~j/v[i])f[i][j]=max(f[i][j],f[i-k][j-k*v[i]]+k*w[i])//優(yōu)化：樸素版本時(shí)：f[i][j] =max{f[i-1][j], f[i-1][j-v[i]]+w[i], f[i-2][j-2*v[i]]+2*w[i]. ······ }f[i][j-v[i]] =max{           f[i-1][j-v[i]],      f[i-2][j-2*v[i]]+w[i]. ······ }由以上兩個(gè)式子可知：不選第i個(gè)：f[i][j]=f[i-1][j]選第i個(gè)（不確定個(gè)數(shù)）：f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);//優(yōu)化為一維f[j]=max(f[j],f[j-v[i]]+w[i])

代碼：

//樸素做法  會(huì)超時(shí)
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n,m;
const int N = 1111;
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=0;j<=m;j++){for(int k=0;k*v[i]<=j;k++){f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i],f[i][j]);}}}cout<<f[n][m];return 0;
}優(yōu)化版本（二維）
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n,m;
const int N = 1111;
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=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i]){f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);}}}cout<<f[n][m];return 0;
}//再優(yōu)化版本（一維）
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n,m;
const int N = 1111;
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=v[i];j<=m;j++){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];return 0;
}

1.3、多重背包

題目:

有n種物品和一個(gè)容量為m的背包，第 i 種物品有s[ i ]件，每件體積是v[ i ]，價(jià)值是w[ i ]，求在不超過背包容量的前提下，可以放的物品的最大價(jià)值是多少

基本思路（二進(jìn)制優(yōu)化版本）：

任何一個(gè)數(shù)可以用二進(jìn)制來表示，也就是2⁰、2¹、……、2ⁿ 其中一項(xiàng)或幾項(xiàng)的和

對(duì)于每一種物品劃分為k組，每組的數(shù)量為2的倍數(shù)

然后轉(zhuǎn)換為01背包進(jìn)行考慮
狀態(tài)設(shè)計(jì)：

同01背包

代碼

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;
const int N=25000;
int n,m;
int w[N],v[N];
int f[N];int main()
{cin>>n>>m;int cnt=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int a,b,s;cin>>a>>b>>s;int k=1;while(s>=k){cnt++;v[cnt]=a*k;w[cnt]=b*k;s-=k;k*=2;}if(s){cnt++;v[cnt]=a*s;w[cnt]=b*s;}}}n=cnt;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]);}}cout<<f[m];
}

1.4、分組背包

題目：

有n件物品（可以被分成幾組）和一個(gè)容量為m的背包，第i件物品的體積是v[ i ]，價(jià)值是w[ i ]，組號(hào)為p[ i ]，每組只能選一個(gè)物品，求在不超過背包容量的前提下，可以放的物品的最大價(jià)值是多少

基本思路：

對(duì)于每組物品考慮取（取哪一件）或者不取

狀態(tài)設(shè)計(jì)：

狀態(tài)表示：f[i][j]集合：從前i組中選，總體積不超過j的物品的價(jià)值屬性：max
狀態(tài)計(jì)算：第i組不選：f[i][j]=f[i-1][j]選第i組的第k個(gè)：f[i][j]=max(f[i-1][j-v[i][k]]+w[i][k])//優(yōu)化為一維f[j]=max(f[j],f[j-v[i][k]]+w[i][k])

代碼：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
int n,m;
int w[110][110],v[110][110];
int s[110];
//二維  int f[110][110];
int f[110];
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];for(int j=1;j<=s[i];j++)  scanf("%d%d",&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];for(int k=0;k<=s[i];k++){if(j-v[i][k]>=0){f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);}}}}cout<<f[n][m];*/for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){f[j]=f[j];for(int k=0;k<=s[i];k++){if(j-v[i][k]>=0){f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);}}}}cout<<f[m];return 0;
}

1.5、混合背包

題目：

將1.1、1.2、1.3三種背包混合起來，即有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數(shù)有一個(gè)上限（多重背包）。

基本思路：

同上，分情況考慮各物品

狀態(tài)設(shè)計(jì)：

同上

例題+代碼：

有N種物品和一個(gè)容量是 V的背包。
物品一共有三類：
第一類物品只能用1次（01背包）；
第二類物品可以用無限次（完全背包）；
第三類物品最多只能用 si 次（多重背包）；
每種體積是 vi，價(jià)值是 wi。
求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價(jià)值總和最大。
輸出最大價(jià)值。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N=1010;int n,m;
int v[N],w[N],s[N];
int f[N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++){scanf("%d%d%d",&v[i],&w[i],&s[i]);if(s[i]==-1)    s[i]=1;}for(int i=1;i<=n;i++){if(s[i]==0){for(int j=v[i];j<=m;j++){f[j]=max(f[j],f[j-v[i]]+w[i]);}}else{for(int k=1;k<=s[i];k*=2){for(int j=m;j>=k*v[i];j--){f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);}s[i]-=k;}if(s[i]){for(int j=m;j>=s[i]*v[i];j--){f[j]=max(f[j],f[j-s[i]*v[i]]+s[i]*w[i]);}}}}cout<<f[m];
}

1.6、二維費(fèi)用的背包

題目：

對(duì)于每種物品有兩個(gè)限制條件，即除了對(duì)體積有限制外，還有一個(gè)限制量

基本思路：

增加了一重限制，所以需要增加一維變量

狀態(tài)設(shè)計(jì)：

狀態(tài)表示：f[i][j][k]集合：從前i個(gè)中選，體積不超過j，重量不超過k的價(jià)值區(qū)間：max
狀態(tài)計(jì)算：同上

代碼：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N=1010;int n,M,W;
int v[N],m[N],w[N];
int f[110][110];int main()
{cin>>n>>M>>W;for(int i=1;i<=n;i++)   scanf("%d%d%d",&v[i],&m[i],&w[i]);for(int i=1;i<=n;i++){for(int j=M;j>=v[i];j--){for(int k=W;k>=m[i];k--){f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);}}}cout<<f[M][W];return 0;
}