藍色代碼膜拜大神C++ 實作 0-1 背包問題
1. 0-1背包問題
問題描述：
有n個物品，第i個物品價值為vi，重量為wi，其中vi和wi均為非負數，背包的容量為W。問如何選擇裝入背包的物品，使裝入背包的物品總價值最大。
考慮一個執行個體，假設n=5，W=17， 每個物品的價值和重量如下表所示。可将物品1，2和5裝入背包，背包未滿，獲得價值22，此時問題解為（1，1，0，0，1）。也可以将物品4和5裝入背包，背包裝滿，獲得價值24，此時解為（0，0，0，1，1）。
基本思路：
這是最基本的背包問題，特點是：每種物品僅有一件，要麼放（即1）要麼不放（即0），是以稱為“0-1背包問題”。
（1）問題分解：
可以将0-1背包問題的求解過程看做進行一系列的決策過程，即決定哪些物品應放入背包，哪些物品不放入背包。如果一個問題的最優解包含了物品n，即背包中放入物品n（xn=1），那麼其餘x1，x2，…，x(n-1)一定構成子問題：1，2，…，n-1在容量為W-wn時的最優解。如果這個最優解不包含物品n，即背包中不放入物品n（xn=0），那麼其餘x1，x2，…，x(n-1)一定構成子問題1，2，…，n-1在容量W時的最優解。
（2）狀态轉移方程：
根據上述分析，最優解問題遞歸地轉化為求子問題的最優解。設c[i,w]表示前i件物品放入一個容量為w的背包可以獲得的最大價值，得到下式：
由上式，我們要求的最優解就是c[n,w]。
（3）僞代碼：
c[0, 0..W] <— 0
for i <— 1 to n
for w <— wi to W
c[i,w] <— max(c[i-1, w],c[i-1, w-wi])
（4）C++代碼：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
/*
0-1 背包問題（疊代版）
輸入：
products_count：商品的數量
capacity：背包的容量
weight_array：商品重量數組
value_array：商品價格數組
result：結果數組
*/
int knapsack(int products_count,int capacity,vector<int> &weights,vector<int> &values,vector<vector<int>> &res){
for(int i=1;i<=products_count;i++){//i個物品
for(int j=1;j<=capacity;j++){//背包容量為j
if(weights[i] > j){//目前背包的容量 j 放不下第 i 件商品時
res[i][j] = res[i-1][j];
}else
{
res[i][j] = max( res[i-1][j-weights[i]] + values[i] , res[i-1][j]);
}
}
}
return res[products_count][capacity];
}
int main(){
int products_count,capacity;
cin>>products_count>>capacity;
vector<int> weights(products_count + 1,0); //注意：這裡變量的長度為products_count +1，
//即從0到products_count（下标為0的全零行是要用到的,見下表格）
vector<int> values(products_count + 1,0);
vector<vector<int>> res(products_count + 1,vector<int> (capacity + 1,0));
for(int i=1;i<=products_count;++i){
cin>>weights[i]>>values[i];
}
int ans = knapsack(products_count,capacity,weights,values,res);
cout<<ans<<endl;
return 0;
}
（5）代碼分析：
上述代碼的時間複雜度為O(商品數量 * 背包容量)。
輸入 5 件商品，重量分别為3、4、7、8、9，價格分别為4、5、10、11、13，背包容量為17。
result 矩陣如下表所示：
簡潔版：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int fun(int n,int v,vector<int> weight,vector<int> price,vector<vector<int>> res){
for(int i=1;i<=n;++i){
for(int j=1;j<=v;++j){
if(weight[i] > j)
res[i][j] = res[i-1][j];
else
res[i][j] = max(res[i-1][j-weight[i]]+price[i],res[i-1][j]);
}
}
return res[n][v];
}
int main(){
int n,v;
cin>>n>>v;
vector<int> weight(n+1,0); //注意：這裡變量的長度為n+1，即從0到n（下标為0的全零行是要用到的）
vector<int> price(n+1,0); //同上
vector<vector<int>> res(n+1,vector<int>(v+1,0));
for(int i=1;i<=n;++i){
cin>>weight[i]>>price[i];
}
int ans = fun(n,v,weight,price,res);
cout<<ans<<endl;
return 0;
}
空間複雜度優化：
以上方法時間和空間複雜度均為O(商品數量 * 背包容量)，其中時間複雜度應該已經不能再優化了，但空間複雜度卻可以優化到O(背包容量)，即将上面所述的二維數組c[i,w]用一維數組代替。狀态轉移方程式：
f[j]=max(f[j],f[j-w[i]]+v[i]
這要求我們在每次主循環中以
for w <— W .. 0
的遞減順序計算c[w]，這樣才能保證計算c[w]時c[w-wi]儲存的是狀态c[i-1,w-wi]的值。
僞代碼如下：
c[0..W] <— 0
for i <— 1 to n
for w <— W to wi
c[w] <— max(c[w],c[w-wi])
C++實作：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int fun(int n,int v,vector<int> weight,vector<int> price,vector<int> res){
for(int i=1;i<=n;++i){
for(int j=v;j>=weight[i];--j){ // 注意：j必須從v開始！！！不同于上述的for(int j=1;j<=v;++j)
res[j] = max(res[j-weight[i]]+price[i],res[j]);
}
}
return res[v];
}
int main(){
int n,v;
cin>>n>>v;
vector<int> weight(n+1,0);
vector<int> price(n+1,0);
vector<int> res(v+1);
for(int i=1;i<=n;++i){
cin>>weight[i]>>price[i];
}
int ans = fun(n,v,weight,price,res);
cout<<ans<<endl;
return 0;
}
2. 恰好裝滿背包
初始化的細節問題：
背包問題有兩種不同的問法：（1）普通問法，即要求價值最大就好，不需要恰好裝滿背包；（2）要求恰好裝滿背包。
- 如果是第一種問法，不要求恰好裝滿背包，而是隻希望價格盡量大，即是上述的代碼，将res[0,n]全部初始化為0；
- 如果是第二種問法，要求恰好裝滿背包，那麼在初始化時除了res[0]為0（0行本來就是全0行），其它res[1…n]均設為負數。這樣就可以保證最終得到的res[n]是一種恰好裝滿背包的最優解。
C++實作：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int fun(int n,int v,vector<int> weight,vector<int> price,vector<int> res){
for(int i=1;i<=n;++i){
for(int j=v;j>=weight[i];--j){// 注意：j必須從v開始！！！不同于上述的for(int j=1;j<=v;++j)
res[j] = max(res[j-weight[i]]+price[i],res[j]);
}
}
return res[v];
}
int main(){
int n,v;
cin>>n>>v;
vector<int> weight(n+1,0);
vector<int> price(n+1,0);
//###這裡将res的1-n全部初始化為-1，而res[0]=0###
vector<int> res(v+1,-1);
res[0]=0;
for(int i=1;i<=n;++i){
cin>>weight[i]>>price[i];
}
int ans = fun(n,v,weight,price,res);
cout<<ans<<endl;
return 0;
}
3. 完全背包問題
問題描述：
有N種物品和一個容量為V的背包，每種物品都有無限件可用。放入第i種物品的費用是ci，價值是wi。求解：将哪些物品裝入背包，可使這些物品耗費的費用總和不超過背包容量，且價值總和最大。
即：完全背包問題在0-1背包問題的基礎上對一個條件進行了更改：每種物品都有無限件可用。
解法思路：
其實，隻要對0-1背包問題的代碼稍加修改就可以變成完全背包問題。先看僞代碼：
F[0..V] <— 0
for i <— 1 to N
for v <— ci to V
F[v] <— max(F[v], F[v-ci]+wi)
可以看到，這個僞代碼與01背包問題的僞代碼隻有v的循環次序不同而已。
為什麼這個算法就可以行呢？01背包問題中讓v遞減是為了保證第i次循環中狀态F[i,v]是由狀态F[i-1,v-ci]遞推而來。換句話說，這正是為了保證每件物品隻選一次。而現在完全背包的特點恰是每種物品可選無限件，是以就可以并且必須采用v遞增的順序循環。
C++實作：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int fun(int n,int v,vector<int> weight,vector<int> price,vector<int> res){
for(int i=1;i<=n;++i){
for (int j = weight[i]; j <=v; ++j) {// ###注意：j必須按遞增順序排列###
res[j] = max(res[j-weight[i]]+price[i],res[j]);
}
}
return res[v];
}
int main(){
int n,v;
cin>>n>>v;
vector<int> weight(n+1,0);
vector<int> price(n+1,0);
vector<int> res(v+1,0);
for(int i=1;i<=n;++i){
cin>>weight[i]>>price[i];
}
int ans = fun(n,v,weight,price,res);
cout<<ans<<endl;
return 0;
}
4. 多重背包問題
問題描述：
有N種物品和一個容量為V的背包。第i種物品最多有mi件可用，每件耗費的空間是ci，簡直是wi。求解将哪些物品裝入背包可使這些物品耗費的空間總和不超過背包容量，且價值總和最大。
樸素算法：
我們可以把mi個物品逐個拆分得到Σmi個物品，即可以将原問題轉換為01背包問題求解，時間複雜度是O(V*Σm)。
C++實作：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int fun(int n, int v, vector<int> weight, vector<int> price,vector<int>cot, vector<int> res) {
for (int i = 1; i <= n; ++i) {
for (int k = 1; k <= cot[i]; k++) {//cot數組為每種物品的數量
for (int j = v; j >= weight[i]; --j) {
res[j] = max(res[j - weight[i]] + price[i], res[j]);
}
}
}
return res[v];
}
int main() {
int n, v;
cin >> n >> v;
vector<int> weight(n + 1, 0);
vector<int> price(n + 1, 0);
vector<int> count(n + 1, 0);
vector<int> res(v + 1);
for (int i = 1; i <= n; ++i) {
cin >> weight[i] >> price[i] >> count[i];
}
int ans = fun(n, v, weight, price, count, res);
cout << ans << endl;
return 0;
}
5. 二維費用的背包問題
問題描述：
對于每件物品，具有兩種不同的費用，選擇這件物品必須同時付出這兩種費用。對于每種費用都由一個可付出的最大值（背包容量）。
算法：
費用加了一維，隻需狀态也加一維即可。設F[i,v,u]表示前i件物品付出兩種費用分别為v和u時可獲得的最大價值。狀态轉移方程就是：
F[i,v,u] = max{ F[i-1,v,u], F[i-1,v-w1_i,u-w2_i]+price_i }
C++實作：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int fun(int n, int v,int v2, vector<int> weight,vector<int> weight2, vector<int> price, vector< vector<int> > res) {
for (int i = 1; i <= n; ++i) {
for (int j = v; j >= weight[i]; --j) { // 注意：j必須從v開始！！！不同于上述的for(int j=1;j<=v;++j)
for (int k = v2; k >= weight2[i]; --k){
res[j][k] = max(res[j - weight[i]][k - weight2[i]] + price[i], res[j][k]);
//res[j] = max(res[j - weight[i]] + price[i], res[j]);
}
}
}
return res[v][v2];
}
int main() {
int n, v,v2;
cin >> n >> v>>v2;
vector<int> weight(n + 1, 0);
vector<int> weight2(n + 1, 0);
vector<int> price(n + 1, 0);
vector< vector<int> > res(v + 1, vector<int>(v2+1));
//vector<int> res(v + 1);
for (int i = 1; i <= n; ++i) {
cin >> weight[i] >>weight2[i]>> price[i];
}
int ans = fun(n, v, v2, weight, weight2, price, res);
cout << ans << endl;
return 0;
}
6. 分組背包問題
問題：
有N件物品和一個容量為V的背包。第i件物品的費用是wi，價值是vi。這些物品被劃分為K組，限定條件是：每組中的物品互相沖突，最多隻能選一件。
算法：
這個問題變成個了每組物品有若幹種政策：是選擇本組的某一件，還是一件都不選。也就是說F[k,v]表示前k組物品花費費用v能取得的最大權值，則有：
F[k,v] = max{ F[k-1,v], F[k-1,v-wi]+vi}
使用一維數組的僞代碼如下：
for k <— 1 to K
for v <—V to 0
for all item i in group k
F[v] <— max{F[v], F[v-wi]+vi}
C++實作：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int fun(int n, int v,int t, vector<int> weight, vector<int> price,vector<vector<int> >group, vector<int> res) {
for (int i = 1; i <= t; ++i) {//i周遊每組
for (int j = v; j >= 0; --j) {//j周遊背包容量
for (int k = 0; k < group[i].size(); k++) {//k周遊i組中物品
int x = group[i][k];//x是第i組第k個物品的下标
if (j >= weight[x]) {
res[j] = max(res[j - weight[x]] + price[x], res[j]);
}
}
}
}
return res[v];
}
int main() {
int n, v;//n物品數，v背包容量
cin >> n >> v;
int t;//g分組數
cin >> t;
vector<int> weight(n + 1, 0);
vector<int> price(n + 1, 0);
vector<int> res(v + 1);
vector<vector<int> > group(t + 1);//###group二維數組的行表示第i組，清單示每組中的物品下标###
int g;//g是每個物品的組号
for (int i = 1; i <= n; ++i) {
cin >> weight[i] >> price[i] >> g;
group[g].push_back(i);//将每個物品的下标添加到group的列中
}
int ans = fun(n, v, t, weight, price, group, res);
cout << ans << endl;
return 0;
}
7. 有依賴的背包問題
問題分析：
這種背包問題的物品間存在某種“依賴”關系：物品i依賴于物品j，表示若選物品i，則必須要選物品j。将不依賴于别的物品的物品成為主件，依賴于某主件的物品成為附件。
C++實作：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int fun(int n, int v, vector<int> weight, vector<int> price, vector<int> q,vector<int> res) {
for (int i = 1; i <= n; ++i) {
for (int j = v; j >= weight[i]; --j) { // 注意：j必須從v開始遞減周遊
if (q[i] == 0)//主件
{
res[j] = max(res[j - weight[i]] + price[i], res[j]);
}
else//附件
{
if (weight[i] + weight[q[i]] <= j)
{
res[j] = max(res[j - weight[i] - weight[q[i]]] + price[i] + price[q[i]], res[j]);
}
}
}
}
return res[v];
}
int main() {
int n, v;//n物品數，v背包容量
cin >> n >> v;
vector<int> weight(n + 1, 0);
vector<int> price(n + 1, 0);
vector<int> res(v + 1);
vector<int> q(n + 1);//q表示該物品是主件還是附件，q=0是主鍵；q>0是附件，q是所屬主件的編号
for (int i = 1; i <= n; ++i) {
cin >> weight[i] >> price[i] >> q[i];
}
int ans = fun(n, v, weight, price, q, res);
cout << ans << endl;
return 0;
}
8. 背包問題的其它問法
8.1 如果要求的是“總價值最小”、“最件數最小”：
隻需将狀态轉移方程中的max改成min即可。
8.2 求方案總數：
将狀态轉移方程中的max改成sum，并且不加上price[i]：
初始條件是F[0,0]=1。