国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

背包九講（超詳細(xì) ：算法分析 + 問題分析 + 代碼分析）

2年前作者：在人間負(fù)債^分類：Toy博客閱讀(20)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了背包九講（超詳細(xì) ：算法分析 + 問題分析 + 代碼分析）。希望對大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

1. 01背包問題

特點(diǎn)：每個(gè)物品只能用一次，只能是選擇或者不選擇

題目鏈接
有 N 件物品和一個(gè)容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的體積是 v_i，價(jià)值是 w_i。

求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價(jià)值最大。
輸出最大價(jià)值。

輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品數(shù)量和背包容積。

接下來有 N 行，每行兩個(gè)整數(shù) v_i,w_i，用空格隔開，分別表示第 i 件物品的體積和價(jià)值。

輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍

0<N,V≤1000
0<v_i,w_i≤1000

輸入樣例：

輸出樣例：

f [ i ][ j ] 表示只看前 i 個(gè)物品，總體積是 j 的情況下，總價(jià)值最大是多少

result = max { f [ n ][ 0 ~ v ] }

f [ i ][ j ] :
1 . 不選第 i 件物品，f [ i ][ j ] = f [ i - 1][ j ];
2 . 選第 i 件物品，f [ i ][ j ] = f [ i - 1][ j - v[ i ] ];
f [ i ][ j ] = max { 1, 2 }

f [ 0 ][ 0 ] = 0;

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=1010;

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

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

優(yōu)化為 1 維的 : f [ i ][ j ] => f [ j ]
f [ j ] 總體是 j 的情況下，總價(jià)值最大是多少

result = max { f[ 0 ~ v ] }; => result = f [ m ]

f [ j ]:
1 . 不選第 i 個(gè)物品，f [ j ] = f [ j ];
2 . 選第 i 個(gè)物品，f [ j ] = f [ j - v [ i ] ];（注意：這個(gè)時(shí)候的循環(huán)要從大到小循環(huán)了）

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]);

f [ j ] = max {1, 2};

result = f [ m ]
1 . 不超過最大體積 m 的最大價(jià)值：f [ 0 ~ v ] = 0;
2 . 體積恰好為 m 的最大價(jià)值：f [ 0 ] = 0，f [ 1 ~ v ] = -∞

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=1010;

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

2. 完全背包問題

特點(diǎn)：每種物品有無限個(gè)，可以選擇 0~n 個(gè)

題目鏈接

有 N 種物品和一個(gè)容量是 V 的背包，每種物品都有無限件可用。

第 i 種物品的體積是 v_i，價(jià)值是 w_i。

求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價(jià)值最大。
輸出最大價(jià)值。

輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品種數(shù)和背包容積。

接下來有 N 行，每行兩個(gè)整數(shù) v_i,w_i，用空格隔開，分別表示第 i 種物品的體積和價(jià)值。

輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍

0<N,V≤1000
0<v_i,w_i≤1000

輸入樣例：

輸出樣例：

f [ i ] 表示總體積是 i 的情況下，最大價(jià)值是多少

result = max { f [ 0 ~ m ] };

f [ i ] :

	for(int i = 1; i <= n; i ++ )
		for(int j = v[i]; j <= m; j ++ )
			f[j] = max([j], [j - v[i]] + w[i]);

result = f [ m ]
1 . 不超過最大體積 m 的最大價(jià)值：f [ 0 ~ v ] = 0;
2 . 體積恰好為 m 的最大價(jià)值：f [ 0 ] = 0，f [ 1 ~ v ] = -∞

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=1010;

int f[N];
int v[N], w[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];
	return 0;
}

3. 多重背包問題

特點(diǎn)：每件物品有 s 件，對于每件物品可以選擇 0 ~ s 件

題目鏈接

有 N 種物品和一個(gè)容量是 V 的背包。

第 i 種物品最多有 s_i 件，每件體積是 v_i，價(jià)值是 w_i。

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

輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品種數(shù)和背包容積。

接下來有 N 行，每行三個(gè)整數(shù) v_i,w_i,s_i，用空格隔開，分別表示第 i 種物品的體積、價(jià)值和數(shù)量。

輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍

0<N,V≤100
0<v_i,w_i,s_i≤100

輸入樣例：

輸出樣例：

f [ i ] 表示總體積是 i 的情況下，最大值是多少

f [ i ] :

for(int i = 1; i <= n; i ++ )
	for(int j = m; j >= v[i]; j -- )
		f[j] = max(f[j], f[j - 1 * v[i]] + 1 * w[i], f[j - 2 * v[i]] + 2 * w[i] ... )

result = f [ m ]
1 . 不超過最大體積 m 的最大價(jià)值：f [ 0 ~ v ] = 0;
2 . 體積恰好為 m 的最大價(jià)值：f [ 0 ] = 0，f [ 1 ~ v ] = -∞

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=1010;

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

題目鏈接

有 N 種物品和一個(gè)容量是 V 的背包。

第 i 種物品最多有 s_i 件，每件體積是 v_i，價(jià)值是 w_i。

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

輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品種數(shù)和背包容積。

接下來有 N 行，每行三個(gè)整數(shù) v_i,w_i,s_i，用空格隔開，分別表示第 i 種物品的體積、價(jià)值和數(shù)量。

輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍

0<N≤1000
0<V≤2000
0<v_i,w_i,s_i≤2000

提示：

本題考查多重背包的二進(jìn)制優(yōu)化方法。

輸入樣例

輸出樣例：

二進(jìn)制優(yōu)化

舉個(gè)栗子：
7 -> 我們可以分解為 7 個(gè) 1 相加，但是這樣分解后，時(shí)間復(fù)雜度并沒有降低
-> 我們還可以分解成 1 、 2 、 4 相加，這樣分解后，時(shí)間復(fù)雜度很明顯就降低了，那么1 、 2 、 4 是怎么來的呢？
2⁰ = 1;
2¹ = 2;
2² = 4;
其實(shí)就是 log₂7 向上取整得到 2 ，所以是 2⁰ - 2² 之間的數(shù)字
這就是乘法原理，利用1 、 2 、 4，我么就可以將 0 - 7 之間的所有數(shù)字表示出來了
如：
0 = 0
1 = 1
2 = 2
3 = 1 + 2
4 = 4
5 = 1 + 4
6 = 2 + 4
7 = 1 + 2 + 4
但是當(dāng) 7 變成 10 呢，繼續(xù)利用 log₂10 向上取整，得到的 3 ，也就是 1 、 2 、 4 、 8，但是此時(shí)表示的最大數(shù)值為 15 ，并不是 10 ，所以，我只選擇 1 、 2 、 4，剩余的數(shù)字直接用 10 - 1 - 2 - 4 - 8 = 3 表示
1 、 2 、 4 可以是表示 0 - 7 之間的全部數(shù)字，
那么 1 、 2 、4 、 3 就可以表示 0 - 10 之間的全部數(shù)字

利用這個(gè)方法，我們就可以把數(shù)據(jù)范圍為 2000 的數(shù)量變成了 log₂2000 ≈ 11 ，這樣我們在繼續(xù)實(shí)現(xiàn)多重背包就可以了

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=1010;

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

struct Good{
	int v, w;
};

int main()
{
	vector<Good> good;
	cin >> n >> m;
	for(int i = 0; i < n; i ++ ) cin >> v[i] >> w[i] >> s[i];
	for(int i = 0; i < n; i ++ )
	{
		// 二進(jìn)制處理 
		for(int j = 1; j <= s[i]; j *= 2 )
		{
			s[i] -= j;
			good.push_back({v[i] * j, w[i] * j});
		}
		if(s[i] >= 0) good.push_back({v[i] * s[i], w[i] * s[i]});
	}
	// 多重背包
	for(auto goods : good)
		for(int j = m; j >= goods.v; j -- )
			f[j] = max(f[j], f[j - goods.v] + goods.w);
	cout << f[m] << endl;
	return 0;
}

題目鏈接

有 N 種物品和一個(gè)容量是 V 的背包。

第 i 種物品最多有 s_i 件，每件體積是 v_i，價(jià)值是 w_i。

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

輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品種數(shù)和背包容積。

接下來有 N 行，每行三個(gè)整數(shù) v_i,w_i,s_i，用空格隔開，分別表示第 i 種物品的體積、價(jià)值和數(shù)量。

輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍

0<N≤1000
0<V≤20000
0<v_i,w_i,s_i≤20000

提示：

本題考查多重背包的單調(diào)隊(duì)列優(yōu)化方法。

輸入樣例

輸出樣例：

基本的多重背包問題狀態(tài)轉(zhuǎn)移方程：
f [ j ] = max ( f [ j ] , f [ j - k * v ] + k * w );
f [ j ] = max ( f [ j ] , f [ j - v ] + w , f [ j - 2 * v ] + 2 * w , f [ j - 3 * v ] + 3 * w … f [ j - s * v ] + s * w )
f [ j - v ] = max ( f [ j - v ] , f [ j - 2 * v ] + w , f [ j - 3 * v ] + 2 * w , f [ j - s * v ] + ( s - 1 ) * w , f [ j - ( s + 1 ) * v ] + s * w )
f [ j - 2 * v ] = …
f [ j - 3 * v ] = …
從上面的 f [ j ] 和 f [ j - v ] 我們可以看出來，相同的部分為：
f [ j - v ] + w , f [ j - 2 * v ] + 2 * w , f [ j - 3 * v ] + 3 * w … f [ j - s * v ] + s * w
f [ j - v ] , f [ j - 2 * v ] + w , f [ j - 3 * v ] + 2 * w , f [ j - s * v ] + ( s - 1 ) * w
因此我們只需要維護(hù) f [ j - v ] 到 f [ j - s * v ] 這個(gè)區(qū)間中的最大值就可以，而維護(hù)一個(gè)區(qū)間的最大值我們就可以使用單調(diào)隊(duì)列來進(jìn)行維護(hù)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=20010;

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

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> v[i] >> w[i] >> s[i];
	for(int i = 0; i < n; i ++ )
	{
		// 滾動(dòng)數(shù)組 
		memcpy(g, f, sizeof f);
		for(int j = 0; j < v[i]; j ++ )
		{
			int hh = 0, tt = -1;
			for(int k = j; k<= m; k += v[i])
			{
				if(hh <= tt && q[hh] < k - s[i] * v[i]) hh ++ ;
				while(hh <= tt && g[q[tt]] - (q[tt] - j) / v[i] * w[i] <= g[k] - (k - j) / v[i] * w[i]) tt -- ;
				q[ ++ tt] = k;
				f[k] = g[q[hh]] + (k - q[hh]) / v[i] * w[i]; 
			}
		} 
	} 
	cout << f[m] << endl;
	return 0;
}

4. 混合背包問題

特點(diǎn)：包含01背包、完全背包、多重背包三種背包問題

題目鏈接

有 N 種物品和一個(gè)容量是 V 的背包。

物品一共有三類：

第一類物品只能用1次（01背包）；
第二類物品可以用無限次（完全背包）；
第三類物品最多只能用 s_i 次（多重背包）；
每種體積是 v_i，價(jià)值是 w_i。

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

輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品種數(shù)和背包容積。

接下來有 N 行，每行三個(gè)整數(shù) v_i,w_i,s_i，用空格隔開，分別表示第 i 種物品的體積、價(jià)值和數(shù)量。

s_i=?1 表示第 i 種物品只能用1次；
s_i=0 表示第 i 種物品可以用無限次；
s_i>0 表示第 i 種物品可以使用 s_i 次；
輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍

0<N,V≤1000
0<v_i,w_i≤1000
?1≤s_i≤1000

輸入樣例

輸出樣例：

對于多重背包，我們利用二進(jìn)制優(yōu)化后，也就是二進(jìn)制分組后，對于每一組都相當(dāng)于01背包，所以在標(biāo)記背包種類的時(shí)候，要標(biāo)記成01背包

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=1010;

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

struct Good{
	int kind;
	int v, w;
};

vector<Good> good;

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> v[i] >> w[i] >> s[i];
    for(int i = 0; i < n; i ++ )
    {
    	if(s[i] == -1) good.push_back({-1, v[i], w[i]});
    	else if(s[i] == 0) good.push_back({0, v[i], w[i]});
    	// 多重背包二進(jìn)制優(yōu)化（分組）之后，對于每一組都相當(dāng)于是01背包 
		else
    	{
    		for(int k = 1; k <= s[i]; k *= 2)
    		{
    			s[i] -= k;
    			good.push_back({-1, v[i] * k, w[i] * k});
			}
			if(s[i] > 0) good.push_back({-1, v[i] * s[i], w[i] * s[i]});
		}
	}
	// 對于01背包和完全背包分兩種情況狀態(tài)轉(zhuǎn)移即可 
	for(auto goods : good)
	{
		// 01背包 
		if(goods.kind == -1)
		{
			for(int j = m; j >= goods.v; j -- )
				f[j] = max(f[j], f[j - goods.v] + goods.w);
		}
		else
		{
			for(int j = goods.v; j <= m; j ++ )
				f[j] = max(f[j], f[j - goods.v] + goods.w); 
		} 
	} 
	cout << f[m] << endl;
	return 0;
}

5. 二維費(fèi)用的背包問題

特點(diǎn)：一般的背包問題，只有一個(gè)容量的限制，對于二維背包問題，除了容量的限制還有另一個(gè)限制，

題目鏈接

有 N 件物品和一個(gè)容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。體積是 v_i，重量是 m_i，價(jià)值是 w_i。

求解將哪些物品裝入背包，可使物品總體積不超過背包容量，總重量不超過背包可承受的最大重量，且價(jià)值總和最大。
輸出最大價(jià)值。

輸入格式
第一行三個(gè)整數(shù)，N,V,M，用空格隔開，分別表示物品件數(shù)、背包容積和背包可承受的最大重量。

接下來有 N 行，每行三個(gè)整數(shù) v_i,m_i,w_i，用空格隔開，分別表示第 i 件物品的體積、重量和價(jià)值。

輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍

0<N≤1000
0<V,M≤100
0<v_i,m_i≤100
0<w_i≤1000

輸入樣例

輸出樣例：

f [ i ][ j ] 表示總體積是 i ，總重量是 j 的情況下，最大價(jià)值是多少

同時(shí)對于狀態(tài)轉(zhuǎn)移的時(shí)候，兩層 for 循環(huán)，一層是體積限制，一層是重量限制

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=1010;

int a, b, c;
int v[N], t[N], w[N];
int f[N][N];

int main()
{
    cin >> a >> b >> c;
    for(int i = 0; i < a; i ++ ) cin >> v[i] >> t[i] >> w[i];
    for(int i = 0; i < a; i ++ )
    	for(int j = b; j >= v[i]; j -- )
    		for(int k = c; k >= t[i]; k -- )
    			f[j][k] = max(f[j][k], f[j - v[i]][k - t[i]] + w[i]);
	cout << f[b][c] << endl;
	return 0;
}

6. 分組背包問題

特點(diǎn)：每一組中有多個(gè)物品，但是同組內(nèi)的物品最多只能選擇一個(gè)

題目鏈接

有 N 組物品和一個(gè)容量是 V 的背包。

每組物品有若干個(gè)，同一組內(nèi)的物品最多只能選一個(gè)。
每件物品的體積是 v_ij，價(jià)值是 w_ij，其中 i 是組號，j 是組內(nèi)編號。

求解將哪些物品裝入背包，可使物品總體積不超過背包容量，且總價(jià)值最大。

輸出最大價(jià)值。

輸入格式
第一行有兩個(gè)整數(shù) N，V，用空格隔開，分別表示物品組數(shù)和背包容量。

接下來有 N 組數(shù)據(jù)：

每組數(shù)據(jù)第一行有一個(gè)整數(shù) S_i，表示第 i 個(gè)物品組的物品數(shù)量；
每組數(shù)據(jù)接下來有 S_i 行，每行有兩個(gè)整數(shù) v_ij,w_ij，用空格隔開，分別表示第 i 個(gè)物品組的第 j 個(gè)物品的體積和價(jià)值；
輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍

0<N,V≤100
0<S_i≤100
0<v_ij,w_ij≤100

輸入樣例

輸出樣例：

對于不同組之間來說就相當(dāng)于普通的背包問題，但是在同一組中，就只能選擇一個(gè)物品，也就是說，選擇了第一組中的第一個(gè)物品，那么第一組中的其他物品就不能夠再選擇了，相反，如果沒有選擇第一組中的第一個(gè)物品，那么就要選擇，第一組中的其他物品，當(dāng)然在選擇的時(shí)候，相當(dāng)于是01背包，所以在選擇物品的時(shí)候，要進(jìn)行判斷
j >= v [ k ]
v [ k ] ：某一組中的某一個(gè)物品的體積

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=1010;

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

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

7. 背包問題求方案數(shù)

特點(diǎn)：在背包問題下，求出最優(yōu)選法的方案數(shù)

題目鏈接

有 N 件物品和一個(gè)容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的體積是 v_i，價(jià)值是 w_i。

求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價(jià)值最大。

輸出最優(yōu)選法的方案數(shù)。注意答案可能很大，請輸出答案模 10⁹+7 的結(jié)果。

輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品數(shù)量和背包容積。

接下來有 N 行，每行兩個(gè)整數(shù) v_i,w_i，用空格隔開，分別表示第 i 件物品的體積和價(jià)值。

輸出格式
輸出一個(gè)整數(shù)，表示方案數(shù) 模 10⁹+7 的結(jié)果。

數(shù)據(jù)范圍

0<N,V≤1000
0<v_i,w_i≤1000

輸入樣例

輸出樣例：

f [ j ] 表示體積恰好是 j 的情況下，最大價(jià)值是多少
g [ j ] 表示體積恰好是 j 的情況下，方案數(shù)是多少

這個(gè)地方的 f [] 數(shù)組的含義與前面的背包問題不一樣，所以在這里的初始化，也與前面不同，這個(gè)地方在前面的背包問題上有所提到
f [ 0 - N ] = -∞
f [ 0 ] = 0，g [ 0 ] = 1

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=1010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int n, m;
int v[N], w[N];
int f[N], g[N];
int main()
{
	cin >> n >> m;
	g[0] = 1;
	for(int i = 1; i <= m; i ++ ) f[i] = -INF;
	for(int i = 0; i < n; i ++ ) cin >> v[i] >> w[i];
	for(int i = 0; i < n; i ++ )
		for(int j = m; j >= v[i]; j -- )
		{
			int t = max(f[j], f[j - v[i]] + w[i]);
			int s = 0;
			if(t == f[j]) s += g[j];
			if(t == f[j - v[i]] + w[i]) s += g[j - v[i]];
			if(s >= mod) s -= mod;
			f[j] = t;
			g[j] = s;
		}
	int maxx = 0;
	for(int i = 0; i <= m; i ++ ) maxx = max(maxx, f[i]);
	int ans = 0;
	for(int i = 0; i <= m; i ++ )
		if(maxx == f[i])
		{
			ans += g[i];
			if(ans >= mod) ans -= mod;
		}
	cout << ans << endl;
	return 0;
}

8. 求背包問題的方案

特點(diǎn)：在普通背包的基礎(chǔ)下，輸出選擇方案，比如選擇物品1 、 3 、 4是最優(yōu)解，那么就輸出 1 、 3 、 4

題目鏈接

有 N 件物品和一個(gè)容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的體積是 v_i，價(jià)值是 w_i。

求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價(jià)值最大。

輸出字典序最小的方案。這里的字典序是指：所選物品的編號所構(gòu)成的序列。物品的編號范圍是 1…N。

輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品數(shù)量和背包容積。

接下來有 N 行，每行兩個(gè)整數(shù) v_i,w_i，用空格隔開，分別表示第 i 件物品的體積和價(jià)值。

輸出格式
輸出一行，包含若干個(gè)用空格隔開的整數(shù)，表示最優(yōu)解中所選物品的編號序列，且該編號序列的字典序最小。

物品編號范圍是 1…N。

數(shù)據(jù)范圍

0<N,V≤1000
0<v_i,w_i≤1000

輸入樣例

輸出樣例：

1 4

我們要輸出所選的方案數(shù)，首先我們按照普通背包的問題求解后，我們會(huì)得到 f [] 數(shù)組，因此如果我們要求出選擇了哪一些物品，我們就可以對 f [] 數(shù)組進(jìn)行反推，
如果 f [ i ][ j ] == f [ i ][ j ] ，說明選擇了第 i 個(gè)物品
如果 f [ i ][ j ] == f [ i - 1 ][ j - v[ i ] ] ，說明選擇了第 i - 1 個(gè)物品
這個(gè)題目為了解唯一，他的答案方案數(shù)是字典序最小的方案，因此我們可以按照貪心的思想去做，如果能選擇第 i 個(gè)物品，那么我們就直接選第 i 個(gè)物品，而不選第 i + 1 個(gè)物品（如果選擇第 i 個(gè)和選擇第 i + 1 個(gè)物品所得到的最大價(jià)值相同的話）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=1010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

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];
	for(int i = n; i >= 1; 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]);
		}
	int vol = m;
	for(int i = 1; i <= n; i ++ )
		if(vol - v[i] >= 0 && f[i][vol] == f[i + 1][vol - v[i]] + w[i])
		{
			cout << i << ' ';
			vol -= v[i];
		}	
	return 0;
}

9. 有依賴的背包問題

特點(diǎn)：N個(gè)物品，V容量的背包，物品之間有依賴關(guān)系，且依賴關(guān)系可以構(gòu)成一棵樹，如果選擇某一個(gè)物品那么就必須先選擇這個(gè)物品的父親物品

題目鏈接

有 N 個(gè)物品和一個(gè)容量是 V 的背包。

物品之間具有依賴關(guān)系，且依賴關(guān)系組成一棵樹的形狀。如果選擇一個(gè)物品，則必須選擇它的父節(jié)點(diǎn)。

如下圖所示：
背包九講（超詳細(xì) ：算法分析 + 問題分析 + 代碼分析）

如果選擇物品5，則必須選擇物品1和2。這是因?yàn)?是5的父節(jié)點(diǎn)，1是2的父節(jié)點(diǎn)。

每件物品的編號是 i，體積是 v_i，價(jià)值是 w_i，依賴的父節(jié)點(diǎn)編號是 p_i。物品的下標(biāo)范圍是 1…N。

求解將哪些物品裝入背包，可使物品總體積不超過背包容量，且總價(jià)值最大。

輸出最大價(jià)值。

輸入格式
第一行有兩個(gè)整數(shù) N，V，用空格隔開，分別表示物品個(gè)數(shù)和背包容量。

接下來有 N 行數(shù)據(jù)，每行數(shù)據(jù)表示一個(gè)物品。
第 i 行有三個(gè)整數(shù) v_i,w_i,p_i，用空格隔開，分別表示物品的體積、價(jià)值和依賴的物品編號。
如果 p_i=?1，表示根節(jié)點(diǎn)。數(shù)據(jù)保證所有物品構(gòu)成一棵樹。

輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍

1≤N,V≤100
1≤v_i,w_i≤100

父節(jié)點(diǎn)編號范圍：

內(nèi)部結(jié)點(diǎn)：1≤p_i≤N;
根節(jié)點(diǎn) p_i=?1;

輸入樣例

輸出樣例：

f [ i ][ j ] 表示選擇結(jié)點(diǎn) i （在這里也就是根節(jié)點(diǎn)），總體積是 j 時(shí)，最大價(jià)值是多少

當(dāng)我們選擇根節(jié)點(diǎn)后，對于根節(jié)點(diǎn)的每一棵子樹，都相當(dāng)于對根節(jié)點(diǎn)做分組背包了，每一個(gè)根節(jié)點(diǎn)相當(dāng)于一個(gè)組，對于組中的節(jié)點(diǎn)分為選擇或者不能選擇文章來源地址http://www.zghlxwxcb.cn/news/detail-401074.html

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>

using namespace std;
typedef long long ll;
const int N=1010;

int n, m;
int v[N], w[N];
int f[N][N];
int h[N], e[N], ne[N], idx;

void add(int a, int b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx ++ ;
}

void dfs(int u)
{
	for(int i = h[u]; i != -1; i = ne[i])
	{
		int son = e[i];
		dfs(son);
		for(int j = m - v[u]; j >= 0; j --)
			for(int k = 0; k <= j; k ++ )
				f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
	}
	// 將根節(jié)點(diǎn) u 加上 
	for(int i = m; i >= v[u]; i -- )
		f[u][i] = f[u][i - v[u]] + w[u];
	// 如果選擇了子節(jié)點(diǎn)后，還沒有選擇到最后的 root ，那么就不能選擇當(dāng)前結(jié)點(diǎn)及其根節(jié)點(diǎn)了 
	for(int i = 0; i < v[u]; i ++ )
		f[u][i] = 0;
}

int main()
{
	cin >> n >> m;
	memset(h, -1, sizeof h);
	int root;
	for(int i = 1; i <= n; i ++ )
	{
		int p;
		cin >> v[i] >> w[i] >> p;
		if(p == -1) root = i;
		else add(p, i);
	}  
	dfs(root);
	cout << f[root][m] << endl; 
	return 0;
}

到了這里，關(guān)于背包九講（超詳細(xì) ：算法分析 + 問題分析 + 代碼分析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

動(dòng)態(tài)規(guī)劃：0-1背包、完全背包問題 | 詳細(xì)原理解釋 | 代碼及優(yōu)化（C++）
目錄 01背包問題描述：簡單描述就是：解析：遞推公式： dp數(shù)組的初始化：遍歷順序：圖解：實(shí)現(xiàn)代碼： dp數(shù)組初始化：遍歷：優(yōu)化：原理：遞推公式：遍歷順序：實(shí)現(xiàn)代碼：初始化：遍歷：完全背包問題描述：解析：實(shí)現(xiàn)代碼： ????????01背包是在M件物品
2024年02月11日
瀏覽(21)
算法分析與設(shè)計(jì)——?jiǎng)討B(tài)規(guī)劃求解01背包問題
假設(shè)有四個(gè)物品，如下圖，背包總?cè)萘繛?，求背包裝入哪些物品時(shí)累計(jì)的價(jià)值最多。我們使用動(dòng)態(tài)規(guī)劃來解決這個(gè)問題，首先使用一個(gè)表格來模擬整個(gè)算法的過程。表格中的信息表示指定情況下能產(chǎn)生的最大價(jià)值。例如， (4, 8)表示在背包容量為8的情況下，前四個(gè)物品的最
2024年02月04日
瀏覽(93)
算法設(shè)計(jì)與分析實(shí)驗(yàn)二：動(dòng)態(tài)規(guī)劃法求解TSP問題和01背包問題
【實(shí)驗(yàn)內(nèi)容】（1）tsp問題：利用動(dòng)態(tài)規(guī)劃算法編程求解TSP問題，并進(jìn)行時(shí)間復(fù)雜性分析。輸入：n個(gè)城市,權(quán)值，任選一個(gè)城市出發(fā)；輸出：以表格形式輸出結(jié)果，并給出向量解和最短路徑長度。（2）01背包問題：利用動(dòng)態(tài)規(guī)劃算法編程求解0-1背包問題，并進(jìn)行時(shí)間復(fù)雜性分
2024年02月03日
瀏覽(20)
【算法】算法學(xué)習(xí)七：動(dòng)態(tài)規(guī)劃 | 背包問題 | 最長公共子串（含源代碼）
背包問題是一種經(jīng)典的組合優(yōu)化問題，通常有兩個(gè)版本：0-1背包問題和無限背包問題。 0-1背包問題是指給定一個(gè)背包容量和一組物品，每個(gè)物品有自己的重量和價(jià)值，要求在不超過背包容量的情況下，選擇一些物品放入背包，使得物品的總價(jià)值最大化。每個(gè)物品只能選擇放入
2024年02月09日
瀏覽(17)
【算法設(shè)計(jì)與分析基礎(chǔ)(第三版)習(xí)題答案】8.2 背包問題和記憶功能
a. 對于下列背包問題的實(shí)例，應(yīng)用自底向上動(dòng)態(tài)規(guī)劃算法求解。 b. a 中的實(shí)例有多少不同的最優(yōu)子集 c. 一般來說，如何從動(dòng)態(tài)規(guī)劃算法所生成的表中判斷出背包問題的實(shí)例是不是具有不止一個(gè)最優(yōu)子集？承重量 W = 6 物品重量價(jià)值 1 3 25 2 2 20 3 1 15 4 4 40 5 5 50 題目中要求使用
2023年04月08日
瀏覽(23)
湘潭大學(xué) 算法設(shè)計(jì)與分析實(shí)驗(yàn) 回溯動(dòng)態(tài)規(guī)劃貪心模擬退火解決背包問題
https://download.csdn.net/download/SQ_ZengYX/88620871 測試用例
2024年02月02日
瀏覽(42)
一本通 1267：【例9.11】01背包問題（詳細(xì)代碼+嚴(yán)謹(jǐn)思路+清晰圖片） C++
經(jīng)典01背包問題這里給你? 3? 種方法!! 目錄 DFS 思路：代碼： DFS+記憶化思路：代碼：動(dòng)態(tài)規(guī)劃思路：代碼：時(shí)間復(fù)雜度：O(2^n) DFS求出所有選法，再用ans記錄價(jià)格最大值由于此題數(shù)據(jù)量較小（其實(shí)2^30=1073741824，這種做法是過不了的，是題目數(shù)據(jù)比較水^_^）如果在考試遇
2024年02月13日
瀏覽(39)
背包問題之0-1背包算法詳解
有5件物品和1個(gè)背包，背包最多只能裝下8公斤的物品。怎樣選擇物品，使得背包能裝下并且得到的價(jià)值最大。物品的重量和價(jià)值如下所示：物品1: 6公斤 ?? 價(jià)值48元物品2: 1公斤?? 價(jià)值7元物品3: 5公斤?? 價(jià)值40元物品4: 2公斤? ? 價(jià)值12元物品5: 1公斤?? 價(jià)值8元可以先考慮
2023年04月09日
瀏覽(22)
【算法宇宙——在故事中學(xué)算法】背包dp之完全背包問題
學(xué)習(xí)者不靈絲相傳，而自杖明月相反，子來此事卻無得失。盡管計(jì)算機(jī)是門嚴(yán)謹(jǐn)?shù)膶W(xué)科，但正因?yàn)閲?yán)謹(jǐn)，所以要有趣味才能看得下去。在筆者的前幾篇算法類文章中，都采用了以小故事作為引入的方式來介紹算法，但在回看的時(shí)候發(fā)現(xiàn)學(xué)術(shù)味還是太濃了，完全沒有想看下去的
2023年04月20日
瀏覽(25)
算法系列--動(dòng)態(tài)規(guī)劃--背包問題(3)--完全背包介紹
??\\\"Su7\\\"?? 作者：Lvzi 文章主要內(nèi)容：算法系列–動(dòng)態(tài)規(guī)劃–背包問題(3)–完全背包介紹大家好,今天為大家?guī)淼氖?算法系列--動(dòng)態(tài)規(guī)劃--背包問題(3)--完全背包介紹鏈接: 完全背包可以發(fā)現(xiàn)完全背包問題和01背包問題還是特比相似的分析: 完全背包問題是 01背包問題的推廣
2024年04月25日
瀏覽(27)

<em id="mcnah"></em>

<ul id="mcnah"></ul>