当前位置:   article > 正文

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

运筹学背包问题例题

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


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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

一维版本待续


完全背包问题

有 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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

优化思路

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

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]);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

这个代码和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]);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

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

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]);//完全背包问题
  • 1
  • 2
  • 3

因为和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]);
    }
  • 1
  • 2
  • 3
  • 4
  • 5

得到优化版本

#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;
} 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

一维版本待续


多重背包问题 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的方案数量

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

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

注意:

  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;
} 
  • 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
推荐阅读
相关标签
  

闽ICP备14008679号