背包九讲（超详细 ：算法分析 + 问题分析 + 代码分析）

1. 01背包问题

特点：每个物品只能用一次，只能是选择或者不选择

题目链接
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围

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

输入样例：

4 5
1 2
2 4
3 4
4 5

输出样例：

8

f [ i ][ j ] 表示只看前 i 个物品，总体积是 j 的情况下，总价值最大是多少

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;
}

优化为 1 维的 : f [ i ][ j ] => f [ j ]
f [ j ] 总体是 j 的情况下，总价值最大是多少

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

f [ j ]:
1 . 不选第 i 个物品，f [ j ] = f [ j ];
2 . 选第 i 个物品，f [ j ] = f [ j - v [ 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]);

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

result = f [ m ]
1 . 不超过最大体积 m 的最大价值：f [ 0 ~ v ] = 0;
2 . 体积恰好为 m 的最大价值：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. 完全背包问题

特点：每种物品有无限个，可以选择 0~n 个

题目链接

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围

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

输入样例：

4 5
1 2
2 4
3 4
4 5

输出样例：

10

f [ i ] 表示总体积是 i 的情况下，最大价值是多少

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 的最大价值：f [ 0 ~ v ] = 0;
2 . 体积恰好为 m 的最大价值：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. 多重背包问题

特点：每件物品有 s 件，对于每件物品可以选择 0 ~ s 件

题目链接

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 s_i 件，每件体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 v_i,w_i,s_i，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围

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

输入样例：

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

输出样例：

10

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 的最大价值：f [ 0 ~ v ] = 0;
2 . 体积恰好为 m 的最大价值：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 种物品和一个容量是 V 的背包。

第 i 种物品最多有 s_i 件，每件体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 v_i,w_i,s_i，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围

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

提示：

本题考查多重背包的二进制优化方法。

输入样例

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

输出样例：

10

二进制优化

举个栗子：
7 -> 我们可以分解为 7 个 1 相加，但是这样分解后，时间复杂度并没有降低
-> 我们还可以分解成 1 、 2 、 4 相加，这样分解后，时间复杂度很明显就降低了，那么1 、 2 、 4 是怎么来的呢？
2⁰ = 1;
2¹ = 2;
2² = 4;
其实就是 log₂7 向上取整得到 2 ，所以是 2⁰ - 2² 之间的数字
这就是乘法原理，利用1 、 2 、 4，我么就可以将 0 - 7 之间的所有数字表示出来了
如：
0 = 0
1 = 1
2 = 2
3 = 1 + 2
4 = 4
5 = 1 + 4
6 = 2 + 4
7 = 1 + 2 + 4
但是当 7 变成 10 呢，继续利用 log₂10 向上取整，得到的 3 ，也就是 1 、 2 、 4 、 8，但是此时表示的最大数值为 15 ，并不是 10 ，所以，我只选择 1 、 2 、 4，剩余的数字直接用 10 - 1 - 2 - 4 - 8 = 3 表示
1 、 2 、 4 可以是表示 0 - 7 之间的全部数字，
那么 1 、 2 、4 、 3 就可以表示 0 - 10 之间的全部数字

利用这个方法，我们就可以把数据范围为 2000 的数量变成了 log₂2000 ≈ 11 ，这样我们在继续实现多重背包就可以了

#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 ++ )
	{
		// 二进制处理 
		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 种物品和一个容量是 V 的背包。

第 i 种物品最多有 s_i 件，每件体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 v_i,w_i,s_i，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数，表示最大价值。

数据范围

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

提示：

本题考查多重背包的单调队列优化方法。

输入样例

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

输出样例：

10

基本的多重背包问题状态转移方程：
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
因此我们只需要维护 f [ j - v ] 到 f [ j - s * 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=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 ++ )
	{
		// 滚动数组 
		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. 混合背包问题

特点：包含01背包、完全背包、多重背包三种背包问题

题目链接

有 N 种物品和一个容量是 V 的背包。

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 s_i 次（多重背包）；
每种体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 v_i,w_i,s_i，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

s_i=−1 表示第 i 种物品只能用1次；
s_i=0 表示第 i 种物品可以用无限次；
s_i>0 表示第 i 种物品可以使用 s_i 次；
输出格式
输出一个整数，表示最大价值。

数据范围

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

输入样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例：

8

对于多重背包，我们利用二进制优化后，也就是二进制分组后，对于每一组都相当于01背包，所以在标记背包种类的时候，要标记成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]});
    	// 多重背包二进制优化（分组）之后，对于每一组都相当于是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背包和完全背包分两种情况状态转移即可 
	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. 二维费用的背包问题

特点：一般的背包问题，只有一个容量的限制，对于二维背包问题，除了容量的限制还有另一个限制，

题目链接

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 v_i，重量是 m_i，价值是 w_i。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行，每行三个整数 v_i,m_i,w_i，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式
输出一个整数，表示最大价值。

数据范围

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

输入样例

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

输出样例：

8

f [ i ][ j ] 表示总体积是 i ，总重量是 j 的情况下，最大价值是多少

同时对于状态转移的时候，两层 for 循环，一层是体积限制，一层是重量限制

#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. 分组背包问题

特点：每一组中有多个物品，但是同组内的物品最多只能选择一个

题目链接

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 v_ij，价值是 w_ij，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

每组数据第一行有一个整数 S_i，表示第 i 个物品组的物品数量；
每组数据接下来有 S_i 行，每行有两个整数 v_ij,w_ij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。

数据范围

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

输入样例

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

输出样例：

8

对于不同组之间来说就相当于普通的背包问题，但是在同一组中，就只能选择一个物品，也就是说，选择了第一组中的第一个物品，那么第一组中的其他物品就不能够再选择了，相反，如果没有选择第一组中的第一个物品，那么就要选择，第一组中的其他物品，当然在选择的时候，相当于是01背包，所以在选择物品的时候，要进行判断
j >= v [ k ]
v [ k ] ：某一组中的某一个物品的体积

#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. 背包问题求方案数

特点：在背包问题下，求出最优选法的方案数

题目链接

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 10⁹+7 的结果。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示 方案数 模 10⁹+7 的结果。

数据范围

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

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例：

2

f [ j ] 表示体积恰好是 j 的情况下，最大价值是多少
g [ j ] 表示体积恰好是 j 的情况下，方案数是多少

这个地方的 f [] 数组的含义与前面的背包问题不一样，所以在这里的初始化，也与前面不同，这个地方在前面的背包问题上有所提到
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. 求背包问题的方案

特点：在普通背包的基础下，输出选择方案，比如选择物品1 、 3 、 4是最优解，那么就输出 1 、 3 、 4

题目链接

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 1…N。

数据范围

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

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例：

1 4

我们要输出所选的方案数，首先我们按照普通背包的问题求解后，我们会得到 f [] 数组，因此如果我们要求出选择了哪一些物品，我们就可以对 f [] 数组进行反推，
如果 f [ i ][ j ] == f [ i ][ j ] ，说明选择了第 i 个物品
如果 f [ i ][ j ] == f [ i - 1 ][ j - v[ i ] ] ，说明选择了第 i - 1 个物品
这个题目为了解唯一，他的答案方案数是字典序最小的方案，因此我们可以按照贪心的思想去做，如果能选择第 i 个物品，那么我们就直接选第 i 个物品，而不选第 i + 1 个物品（如果选择第 i 个和选择第 i + 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][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. 有依赖的背包问题

特点：N个物品，V容量的背包，物品之间有依赖关系，且依赖关系可以构成一棵树，如果选择某一个物品那么就必须先选择这个物品的父亲物品

题目链接

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i，体积是 v_i，价值是 w_i，依赖的父节点编号是 p_i。物品的下标范围是 1…N。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。

接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数 v_i,w_i,p_i，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 p_i=−1，表示根节点。 数据保证所有物品构成一棵树。

输出格式
输出一个整数，表示最大价值。

数据范围

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

父节点编号范围：

• 内部结点：1≤p_i≤N;
• 根节点 p_i=−1;

输入样例

5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2

输出样例：

11

f [ i ][ j ] 表示选择结点 i （在这里也就是根节点），总体积是 j 时，最大价值是多少

当我们选择根节点后，对于根节点的每一棵子树，都相当于对根节点做分组背包了，每一个根节点相当于一个组，对于组中的节点分为选择或者不能选择文章来源地址https://www.toymoban.com/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]);
	}
	// 将根节点 u 加上 
	for(int i = m; i >= v[u]; i -- )
		f[u][i] = f[u][i - v[u]] + w[u];
	// 如果选择了子节点后，还没有选择到最后的 root ，那么就不能选择当前结点及其根节点了 
	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;
}

到了这里，关于背包九讲（超详细 ：算法分析 + 问题分析 + 代码分析）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！