01背包問題

有n個物品和一個容量為v的背包，每一個物品有兩個屬性（體積v，價值w），每件物品最多只用一次，在所有物品中選擇的物品總體積最小（小于背包容量），價值最大，

利用動態規劃解決，

相關題目

題目鏈接

原題鏈接

題目描述

有 N 件物品和一個容量是 V 的背包，每件物品只能使用一次，
第 i 件物品的體積是 vi，價值是 wi，
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大，
輸出最大價值，

輸入格式

第一行兩個整數，N，V，用空格隔開，分別表示物品數量和背包容積，
接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分別表示第 i 件物品的體積和價值，

輸出格式

輸出一個整數，表示最大價值，

資料范圍

0< N,V ≤1000
0 < vi,wi ≤1000

輸入樣例

4 5
1 2
2 4
3 4
4 5

輸出樣例：

8

難度：簡單

時/空限制：1s / 64MB

來源：背包九講 , 模板題

演算法標簽

背包問題、DP

代碼思路

二維代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int n , m;
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];

    //f[0][0~m]都是0，但由于f[][]是全域變數，初始化就是0，則i從1開始 ↓
    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]);   
        }

    cout << f[n][m] << endl;

    return 0;
}

一維版

為什么一維情況下列舉背包容量需要逆序？在二維情況下，狀態f[i][j]是由上一輪i - 1的狀態得來的，f[i][j]與f[i - 1][j]是獨立的，而優化到一維后，如果我們還是正序，則有f[較小體積]更新到f[較大體積]，則有可能本應該用第i-1輪的狀態卻用的是第i輪的狀態，

例如，一維狀態第i輪對體積為 3 的物品進行決策，則f[7]由f[4]更新而來，這里的f[4]正確應該是f[i - 1][4]，但從小到大列舉j這里的f[4]在第i輪計算卻變成了f[i][4]，當逆序列舉背包容量j時，我們求f[7]同樣由f[4]更新，但由于是逆序，這里的f[4]還沒有在第i輪計算，所以此時實際計算的f[4]仍然是f[i - 1][4]，

簡單來說，一維情況正序更新狀態f[j]需要用到前面計算的狀態已經被「污染」，逆序則不會有這樣的問題，

狀態轉移方程為：f[j] = max(f[j], f[j - v[i]] + w[i] ，

關于狀態f[j]的補充說明
二維下的狀態定義f[i][j]是前 i 件物品，背包容量 j 下的最大價值，一維下，少了前 i 件物品這個維度，我們的代碼中決策到第 i 件物品（回圈到第i輪），f[j]就是前i輪已經決策的物品且背包容量 j 下的最大價值，

因此當執行完回圈結構后，由于已經決策了所有物品，f[j]就是所有物品背包容量 j 下的最大價值，即一維f[j]等價于二維f[n][j]，

該部分來源：【AcWing】 深藍
鏈接：https://www.acwing.com/solution/content/1374/

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int n , m;
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 = m;j >= v[i];j --)
		{
		//	f[i][j] = f[i-1][j];  一維狀態下：f[j] = f[j]恒等式，刪 
		//	if(j >= v[i])
			f[j] = max(f[j] , f[j - v[i]] + w[i]);	
		}
	
	cout << f[m] << endl;
	
	return 0;
}

//f[i][j]只用到了f[i-1][j]，則可以使用滾動陣列 f[j] 

完全背包問題

有n個物品和一個容量為v的背包，每一個物品有兩個屬性（體積v，價值w），每件物品有無限個，

相關題目

原題鏈接

題目描述

有 N 種物品和一個容量是 V 的背包，每種物品都有無限件可用，
第 i 種物品的體積是 vi，價值是 wi，
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大，
輸出最大價值，

輸入格式

第一行兩個整數，N，V，用空格隔開，分別表示物品種數和背包容積，
接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分別表示第 i 種物品的體積和價值，

輸出格式

輸出一個整數，表示最大價值，

資料范圍

0<N,V≤1000
0<vi,wi≤1000

輸入樣例

4 5
1 2
2 4
3 4
4 5

輸出樣例：

10

難度：簡單

時/空限制：1s / 64MB

總通過數：78845
總嘗試數：140268

來源：背包九講 , 模板題

演算法標簽

背包、問題DP

思路

樸素版（三維）

會超時

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int w[N] , v[N];
int f[N][N];
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 = 0;j <= m;j ++)
			for(int k = 0;k*v[i] <= j;k ++)
				f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
		
	cout << f[n][m] << endl;
	
	return 0;
}

二維優化版

轉自【AcWing 】Charles__

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int w[N] , v[N];
int f[N][N];
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 = 0;j <= m;j ++)
			{
				f[i][j] = f[i-1][j];
				
				if(j - v[i] >= 0)
					f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);
			}
		
	cout << f[n][m] << endl;
	
	return 0;
}

一維優化版

根據二位優化版，可以看出與01背包問題類似，則可以根據01背包問題進行優化

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 1010;

int w[N] , v[N];
int f[N];
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 = v[i];j <= m;j ++)
				f[j] = max(f[j],f[j-v[i]]+w[i]);
			
		
	cout << f[m] << endl;
	
	return 0;
}

多重背包問題

有n個物品和一個容量為v的背包，每一個物品有兩個屬性（體積v，價值w），每個物品最多有s[i]個

樸素版

題目鏈接

原題鏈接

題目描述

有 N 種物品和一個容量是 V 的背包，

第 i 種物品最多有 si 件，每件體積是 vi，價值是 wi，

求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價值總和最大，
輸出最大價值，

輸入格式

第一行兩個整數，N，V，用空格隔開，分別表示物品種數和背包容積，

接下來有 N 行，每行三個整數 vi,wi,si，用空格隔開，分別表示第 i 種物品的體積、價值和數量，

輸出格式

輸出一個整數，表示最大價值，

資料范圍

0<N,V≤100
0<vi,wi,si≤100

輸入樣例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

輸出樣例：

10

難度：簡單

時/空限制：1s / 64MB

來源：背包九講 , 模板題

演算法標簽

背包問題、DP

思路

與完全背包類似

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 110;

int v[N] , w[N] , s[N];
int f[N][N];
int n , m;

int main()
{
	cin >> n >> m;
	
	for(int i = 1;i <= n;i ++)
		cin >> v[i] >> w[i] >> s[i];
	
	for(int i = 1;i <= n;i ++)
		for(int j = 0;j <= m;j ++)
			for(int k = 0;k <= s[i] && k*v[i] <= j;k ++)
				f[i][j] = max(f[i][j] , f[i-1][j-k*v[i]]+k*w[i]);
	
	cout << f[n][m] << endl;
	
	
	return 0;
}

優化

分組背包問題

有n組物品，每組物品有若干個，每組最多選1個

標籤：其他

上一篇：【JS】5. 最長回文子串（待更新中）

下一篇：素數演算法（Prime Num Algorithm）