目录

一、01背包问题

二维dp解法:

一维dp解法:

二、完全背包问题

​编辑

朴素写法(三重循环):

第一次优化:

第二次优化:

三、多重背包问题

多重背包I

思路:

多重背包II

二进制优化方法:

四、分组背包问题

思路:


一、01背包问题

有 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

二维dp解法:

动态规划数组定义

f[i][j]表示只考虑前i件物品,当背包容量为j时的最大价值。

初始化:

// f[0][0~m] = 0; 考虑0件物品,总体积不超过0~m的最大价值
// 由于此时一件物品都没有所以最大价值都0
// 由于之前在前面已经在全局变量中初始化过,所以此处不用再初始化

由上图,我们可以清楚的知道01背包最大价值是如何推出的

状态转移方程:对于每个物品i,我们有两种选择:不放入背包,或者放入背包。如果不放入背包,那么f[i][j] = f[i-1][j];如果放入背包,前提是背包的容量j大于等于物品i的体积v[i],那么f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])。选择这两种情况的最大值作为f[i][j]的值。

循环遍历: 

当前背包容量为 i 时所得最大价值,必不小于背包容量为 i - 1 时的最大价值,故先令此时背包容量的最大价值为 f[i - 1][j],再判断是否能放的下每个不同的物品,如果能放下,则比较后取较大的值。

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]);
	}
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m, v[N], w[N], 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; 考虑0件物品,总体积不超过0~m的最大价值
	// 由于此时一件物品都没有所以最大价值都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]);
		}
	cout << f[n][m] << endl;

	return 0;
}

一维dp解法:

动态规划数组定义

f[j]表示背包容量为j时,能装入的最大价值。

状态转移方程

对于每个物品i,考虑是否放入背包中。若不放入,则总价值不变;

若放入,则总价值为f[j-v[i]] + w[i](在当前容量下,放入物品i后的总价值)。

因此,状态转移方程为f[j] = max(f[j], f[j-v[i]] + w[i])

循环遍历

在01背包问题中,每个物品只能放一次进背包。

如果我们从最小的背包容量开始考虑放物品(即正序遍历),那么在更新较大的背包容量 j 时,较小的背包容量 j-v[i] 可能已经考虑过了物品 i。这会导致物品 i 被错误地计算两次,即它在更新 f[j-v[i]] 时被考虑过一次,在更新 f[j] 时又被考虑。因为逆序是从大到小考虑,所以,并不会发生上述重复考虑的情况( 内层循环中,逆序一开始时,先考虑最大的容量是否能放入,这样处理,就可以使f[j-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]);
		f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
		// 此时上述f[j]与上述f[i][j]等价
		// 可是我们需要得到这个式子的效果
		f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
	}
}

我们发现i与i - 1 差了1, 所以顺序无法得出答案,所以我们选择逆序。

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

外层循环遍历所有物品。

内层循环从m逆序遍历到v[i](物品体积),确保每个物品只被计算一次,防止一个物品被重复计算(即确保每个物品只被放入一次)。

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m, v[N], w[N], 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[j],即考虑放入当前物品i时的最大价值
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

	cout << f[m] << endl;

	return 0;
}

二、完全背包问题

有 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

朴素写法(三重循环):

解题思路:

动态规划数组定义

使用二维数组f[i][j],其中f[i][j]表示考虑前i件物品,当背包容量为j时的最大价值。

状态转移方程:

f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k),这个方程考虑了不选取当前物品和选取当前物品k次两种情况下的最大价值,并取这些情况的最大值更新DP数组。

循环遍历:

  • 外层循环遍历所有物品,中层循环遍历所有可能的背包容量。
  • 内层循环遍历每个物品的可能选取次数k(即物品i可以被选取0次、1次、2次,直到k * v[i]超过当前背包容量j)。
  • 对于每种情况,更新f[i][j]max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k),表示考虑选取k次物品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 - v[i] * k] + w[i] * k);
			}
		}
	}
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

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

	return 0;
}

第一次优化:

解题思路:

动态规划数组定义

使用二维数组f[i][j],其中f[i][j]表示考虑前i件物品,当背包容量为j时的最大价值。

状态转移方程:

如图,我们可以发现f[i,j] = max(f[i-1,j],f[i,j-v]+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]);
		}
	}

 和01背包二维dp类似,当前背包容量为 i 时所得最大价值,必不小于背包容量为 i - 1 时的最大价值,故先令此时背包容量的最大价值为 f[i - 1][j],再判断是否能放的下每个不同的物品,如果能放下,则比较后取较大的值。

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m, v[N], w[N], 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] << endl;

	return 0;
}

第二次优化:

与01背包一维dp类似,但是此处是顺序。

对于完全背包,由于每种物品可以取无限次,我们希望每个物品能够被重复考虑。因此,我们采用正序遍历背包容量的方式(即从 v[i] 到 m)。这样,在更新 f[j] 的时候,f[j-v[i]] 总是表示未选择当前物品 i 时的最大价值,因此当前物品可以被多次加入背包中,只要不超过背包容量。

因为顺序从小到大考虑,已经让每个物品被重复多次的考虑了(f[i,j-v] + w[i]已经多次重复考虑计算之前的物品,顺序时,只要有能放入的空间,就放入物品)

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m, v[N], w[N], 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] << endl;

	return 0;
}

三、多重背包问题

多重背包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

思路:

完全背包问题是第i件物品可以选任意多个,而多重背包只限制了第i件物品最多选s[i]

加上这条限制即可

状态转移方程:

f[i,j] = max(f[i - 1][j - v[i] * k] + w[i] * k); k = 0, 1, 2, 3 ..., s[i]

循环遍历:

外层循环:循环遍历所有物品

中层循环:循环遍历所有可能的背包容量

内层循环:这个循环用于考虑当前物品i可以被选择的数量,k代表选择当前物品的数量。
循环的条件k <= s[i] && k * v[i] <= j确保了两个限制:不超过物品的最大可选数量s[i],以及所选物品的总体积k * v[i]不超过当前背包容量j

此时的时间复杂度为:100*100*100,可以正常运行。

	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 - v[i] * k] + w[i] * k);
			}
		}
	}

此题如果直接使用,时间复杂度为:

#include<bits/stdc++.h>
using namespace std;

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

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 - v[i] * k] + w[i] * k);
			}
		}
	}
	cout << f[n][m] << endl;

	return 0;
}

多重背包II

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

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

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

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

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

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

数据范围:
0 < N ≤ 1000
0 < V ≤ 2000
0 < vi, wi, si ≤ 2000

提示:

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

输入样例

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

输出样例:

10

思路:

该题与多重背包I的区别是数据范围变大,此时如果仍使用多重背包I中的方法,此时的时间复杂度为:1000*2000*2000 = 40亿,,时间复杂度过大需要优化。

二进制优化方法:

简而言之,就是先把同类的物品拆分成不同的组,拆分完一类物品后,再去拆下一个,将所有物品都拆分好后,就将多重背包问题转化为了01背包问题。

#include<bits/stdc++.h>

using namespace std;

const int N = 25000, M = 2010;
//   1000*log2000
int n, m, v[N], w[N], f[N];

int main()
{
	cin >> n >> m;
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		int a, b, s; cin >> a >> b >> s;
		int k = 1;
		while (k <= s)
		{
			cnt++;
			v[cnt] = a * k;
			w[cnt] = b * k;
			s -= k;
			k *= 2;
		}
		if (s > 0)
		{
			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] << endl;

	return 0;
}

四、分组背包问题

给定N组物品和一个容量为V的背包。每组物品包含若干个,但在同一组内,你最多只能选择一件物品。每件物品有其对应的体积和价值。目标是选择一些物品放入背包,使得背包内物品的总体积不超过背包的容量,同时背包内物品的总价值尽可能大。

输入:

第一行输入包含两个整数N和V,分别代表物品组数和背包的容量。
接下来是N组数据。每组数据的第一行包含一个整数s_i,代表第i组的物品数量。
每组数据接下来的s_i行,每行包含两个整数v_{i,j}w_{i,j},分别代表第i组中第j个物品的体积和价值。
输出:

输出一个整数,代表可以放入背包中的物品的最大价值。
数据范围:

0 < N, V ≤ 100
0 < Si ≤ 100
0 < vij, wij ≤ 100

输入样例

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

输出样例:

8

思路:

分组背包问题就是在01背包问题的基础之上,多了一个在每个组中选出最优的那个物品(或者不选)。

for (int i = 1; i <= n; ++i) // 遍历每一组物品  
{  
    for (int j = m; j >= 0; --j) // 遍历背包容量从m到0  
    {  
        for (int k = 0; k < s[i]; ++k) // 遍历第i组中的每个物品  
        {  
            if (v[i][k] <= j) // 如果当前物品可以放入背包中  
            {  
                // 更新背包的最大价值,考虑放入当前物品或不放入的情况  
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);  
            }  
        }  
    }  
}

对于每一组物品,尝试将组中的每个物品放入背包中,看看是否能够得到更大的价值。注意,中层循环是从背包容量m到0的逆序遍历,这是为了防止同一个组中的物品被重复放入背包(即保证每组中至多选择一个物品)。 

#include<bits/stdc++.h>
using namespace std;

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

int main()
{
	cin >> n >> m;

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

	cout << f[m] << endl;

	return 0;
}

今天就先到这了!!!

看到这里了还不给博主扣个:
⛳️ 点赞☀️收藏 ⭐️ 关注!

你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。

Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐