知新_RL

这个屌丝很懒，什么也没留下！

热门标签

背包问题例题_运筹学背包问题例题

作者：知新_RL | 2024-04-10 23:10:32

踩

运筹学背包问题例题

背包问题例题

01背包问题
完全背包问题
多重背包问题 I
多重背包问题 II
数字组合
自然数拆分

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

多重背包问题 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;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

多重背包问题 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;	
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

数字组合

不是很懂

给定 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的方案数量

解法一：二维数组+动态规划
状态转移方程：

不选i：dp[i][j] = dp[i-1][j]
选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;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

自然数拆分

没有很懂

给定一个自然数 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]

注意：

和一般的多重背包状态更新不一样，
这道题不能用 k 次循环更新，否则会计算重复。
更新的过程中 j 从 i 开始循环，在 i 之前没有意义。
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;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

非压缩版（二维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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

压缩版（一维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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/401541