博客

背包问题例题

  • Post author:
  • Post category:其他


背包问题例题

目前仅仅全部掌握二维版本



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


二维版本


（1）状态f[i][j]定义：前 i 个物品，背包容量 j 下的最优解（最大价值）：

当前的状态依赖于之前的状态，可以理解为从初始状态f[0][0] = 0开始决策，有 N 件物品，则需要 N 次决 策，每一次对第 i 件物品的决策，状态f[i][j]不断由之前的状态更新而来。

（2）当前背包容量不够（j < v[i]），没得选，因此前 i 个物品最优解即为前 i−1 个物品最优解：

对应代码：f[i][j] = f[i – 1][j]。

（3）当前背包容量够，可以选，因此需要决策选与不选第 i 个物品：

选：f[i][j] = f[i – 1][j – v[i]] + w[i]。

不选：f[i][j] = f[i – 1][j] 。

我们的决策是如何取到最大价值，因此以上两种情况取 max() 。 

#include <iostream>
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];
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            if (j < v[i]) f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);   
        }
    cout << f[n][m];
    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


二维版本


在这里插入图片描述 

// 优化前
#include <iostream>
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];
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 0; j <= m; j ++ ) {
            if (j < v[i]) f[i][j] = f[i - 1][j];
            else 
                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];
    return 0;
}


优化思路


我们列举一下更新次序的内部关系：

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2 * v]+2 * w , f[i-1,j-3 * v]+3 * w , …)

f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2 * v]+w , f[i-1,j-3 * v]+2 * w , …)

由上两式，可得出如下递推关系：


f[i][j] = max( f[i,j-v]+w , f[i-1][j] )


有了上面的关系，那么其实k循环可以不要了，核心代码优化成这样：
 

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


这个代码和01背包的非优化写法很像啊!!!我们对比一下，下面是01背包的核心代码
 

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


两个代码其实只有一句不同（注意下标）
 

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题


因为和01背包代码很相像，我们很容易想到进一步优化。核心代码可以改成下面这样
 

 for(int i = 1 ; i<=n ;i++)
    for(int j = v[i] ; j<=m ;j++)//注意了，这里的j是从小到大枚举，和01背包不一样
    {
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    }


得到优化版本
 

#include <iostream>
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];
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ ) {
			if (j < v[i]) f[i][j] = f[i - 1][j];
			else f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
		}
	cout << f[n][m];
	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 

#include <iostream>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int 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 ++ ) {
			f[i][j] = f[i - 1][j];
			if (j >= v[i]) 
				for (int k = 1; k * v[i] <= j && k <= s[i]; k ++ ) 
					f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
		}
	cout << f[n][m];
	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


二进制优化的方法


假设有一组商品，一共有11个。我们知道，十进制数字 11 可以这样表示

11=1011(B)=0111(B)+(11−0111(B))=0111(B)+0100(B)

正常背包的思路下，我们要求出含这组商品的最优解，我们要枚举12次（枚举装0，1，2…12个）。

现在，如果我们把这11个商品分别打包成含商品个数为1个，2个，4个，4个（分别对应0001,0010,0100,0100）的四个”新的商品 “, 将问题转化为01背包问题，对于每个商品，我们都只枚举一次，那么我们只需要枚举四次 ，就可以找出这含组商品的最优解。 这样就大大减少了枚举次数。

这种优化对于大数尤其明显，例如有1024个商品，在正常情况下要枚举1025次 ， 二进制思想下转化成01背包只需要枚举10次。


优化的合理性的证明


先讲结论：上面的1，2，4，4是可以通过组合来表示出0~11中任何一个数的，还是拿11证明一下（举例一下）：

首先，11可以这样分成两个二进制数的组合：

11=0111(B)+(11−0111(B))=0111(B)+0100(B)

其中0111通过枚举这三个1的取或不取（也就是对0001(B)，0010(B)，0100(B)的组合），可以表示十进制数0 ~ 7( 刚好对应了 1，2，4 可以组合出 0 ~ 7 ) , 0 ~ 7的枚举再组合上0100(B)( 即 十进制的 4 ) ，可以表示十进制数 0~11。其它情况也可以这样证明。这也是为什么，这个完全背包问题可以等效转化为01背包问题，有木有觉得很奇妙

如果仍然不是很能理解的话，取这样一个例子:要求在一堆苹果选出n个苹果。我们传统的思维是**一个一个地去选，选够n个苹果就停止。**这样选择的次数就是n次

二进制优化思维就是：现在给出一堆苹果和10个箱子，选出n个苹果。将这一堆苹果分别按照1,2,4,8,16,…512分到10个箱子里，那么由于任何一个数字x ∈[1,1024]

都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是

≤10次

。

这样利用二进制优化，时间复杂度就从O(n^3 )降到O(n^2logS ),从4* 10^9 降到了2*10^7。


一维相关


（1）

状态f[j]定义：N 件物品，背包容量 j 下的最优解。

（2）

注意枚举背包容量 j 必须从m开始。

（3）**为什么一维情况下枚举背包容量需要逆序？**在二维情况下，状态f[i][j]是由上一轮i – 1的状态得来的，f[i][j]与f[i – 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

（4）例如，一维状态第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]。

（5）简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。


状态转移方程为：f[j] = max(f[j], f[j – v[i]] + w[i] 。
 

#include <iostream>
#include <vector>
using namespace std;
const int N = 101000;
int n, m;
int f[N];
struct good {
	int v;
	int w;
};
int main()
{
	cin >> n >> m;
	vector<good> goods;
	for (int i = 1; i <= n; i ++ ) {
		int a, b, c;
		cin >> a >> b >> c;
		for (int k = 1; k <= c; k *= 2) {
			c -= k;
			goods.push_back({a * k, b * k});
		}
		if (c > 0) goods.push_back({a * c, b * c});
	}
	for (auto t : goods)
		// 逆序是必须的
		// 如果正序则会使用到当前i的数据，而需要使用的是i-1的数据
		// 例如当计算f[7]时，逆序使用的是未更新的f[6][7]和f[6][7-v]
		// 正序使用的是已更新的f[7][7]和f[7][7-v]
		for (int i = m; i >= t.v; i -- ) 
			f[i] = max(f[i], f[i - t.v] + t.w);
	cout << f[m];
	return 0;	
}



数字组合

不是很懂

给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。


输入格式


第一行包含两个整数 N 和 M。

第二行包含 N 个整数，表示 A1,A2,…,AN。


输出格式


包含一个整数，表示可选方案数。


数据范围


1 ≤ N ≤ 100,

1 ≤ M ≤ 10000,

1 ≤ Ai ≤ 1000,

答案保证在 int 范围内。


输入样例：

4 4

1 1 2 2


输出样例：

3

在这里插入图片描述


可以转化为01背包问题求方案数：

  • 将总和 M 看作背包容量；
  • 将每个数 Ai 看作体积为 Ai 的物品；


时间复杂度


背包问题的时间复杂度是 O(nm)。


二维方法


i：前i个元素

j：当前可用空间

A[i]：第i个物品的空间大小

dp[i,j]：表示在i个元素中选取的总空间等于j的方案数量


解法一：二维数组+动态规划



状态转移方程：

  1. 不选i：dp[i][j] = dp[i-1][j]
  2. 选i：dp[i][j] = dp[i-1][j-A[i]]

    所以总的方案数就1和2的和


解法二：一位数组+动态规划


因为在解法一中，状态转移方程只使用到了i-1和j-a[i]，所以对于二维数组来说，其他记录的状态都是多余的，所以我们可以使用

滚动数组

来对解法一进行优化


状态转移方程：

dp[j] += dp[j-a[i]]

注意：当变为dp[j] += dp[j-a[i]]后，对应的二维状态转移方程为：dp[j][j] += dp[j][j-a[i]]和原二维转移方程矛盾，因为在顺序遍历过程中会导致i-1层的数据先被覆盖，所以需要

逆序遍历

，这样就会先计算高层元素而不会影响底层元素 

// 二维
#include <iostream>
using namespace std;
const int N = 110, M = 10010;
int n, m;
int a[N];
int f[N][M];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	f[0][0] = 1; // 前0个物品体积和为0的方案为1
	for (int i = 1; i <= n; i ++ )
		for (int j = 0; j <= m; j ++ ) {
		    f[i][j] = f[i - 1][j];
		    if (j >= a[i])
		        f[i][j] = f[i][j] + f[i - 1][j - a[i]]; // f[i][j] = f[i - 1][j] + f[i - 1][j - a[i]];
		}
	cout << f[n][m];
	return 0;
}
// 一维
#include <iostream>
using namespace std;
const int N = 10010;
int n, m;
int f[N];
int main()
{
	cin >> n >> m;
	f[0] = 1; // 一个都不选，可以组成0一种方案
	for (int i = 1; i <= n; i ++ ){
		int a;
		cin >> a;
		// j可以看成是现在的方案数加上组成j-a[i]的当前方案数
		// 也可以看做二维表示中推导的状态转移方程的第二维向量
		// j也可以看做，不包括物品i的所有选法加上包括i的所有选法j-a[i] 
		for(int j = m; j >= a; j -- ) f[j] += f[j - a]; 
	}
	cout << f[m];	
	return 0;
}



自然数拆分

没有很懂

给定一个自然数 N，要求把 N 拆分成若干个正整数相加的形式，参与加法运算的数可以重复。


注意:

  • 拆分方案不考虑顺序；
  • 至少拆分成 2 个数的和。

求拆分的方案数 mod2147483648 的结果。


输入格式


一个自然数 N。


输出格式


输入一个整数，表示结果。


数据范围


1 ≤ N ≤ 4000


输入样例：

7


输出样例：

14


状态表示：


f[i][j] 表示前 i 个物品， 组合成权值为 j 的种类数

属性：种类数

要求方案划分不重不漏。


状态计算：


题目要求不考虑顺序，也就是 1 + 2 和 2 + 1 是同一种类型。

而且 3 = 3 不算一种方案。


f[i][j] = f[i-1][j] + f[i-1][j-i]


注意：

  1. 和一般的多重背包状态更新不一样，

    这道题不能用 k 次循环更新，否则会计算重复。
  2. 更新的过程中 j 从 i 开始循环，在 i 之前没有意义。
  3. 2147483648 爆int 用LL来存。 
#include <iostream>
using namespace std;
const int mod = 2147483648, N = 4010;
int n;
long long f[N];
int main()
{
	cin >> n;
	f[0] = 1;
	for (int i = 1; i < n; i ++ ) 
		for (int j = i; j <= n; j ++ )
			f[j] = (f[j] + f[j - i]) % mod;
	cout << f[n];	
	return 0;
}


非压缩版（二维DP）


思路：可以当做是完全背包问题。其中需要凑出来的数看做背包的容量n，物品的体积为1~n，且每种物品都有无数个。 

#include<iostream>
using namespace std;

//【重要】f[i][j]表示i个数的和为j的可能性
//如果选择第i个数，相当于选择值i。
const int N = 4010;
unsigned f[N][N];
int main() {
    int n;
    cin >> n;
    for (int j = 0; j <= n; j++) f[1][j] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= i)
                for (int k = 1; k * i <= j; k++)
                    f[i][j] += f[i - 1][j - k * i];
        }
    }
    cout << (f[n][n] - 1) % 2147483648u << endl;
    return 0;
}


压缩版（一维DP）
 

#include<iostream>
using namespace std;

const int N = 4010;
unsigned f[N];
int main() {
    int n;
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            f[j] += f[j - i];
    cout << (f[n] - 1) % 2147483648u << endl;
    return 0;
}


版权声明：本文为qq_45896050原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。