背包问题研究了好几天,总算是有点头绪了,今天我就把我学到的背包问题整理一下,供各位大佬交流学习,直接开始:

目录:
1、数组递推
2、完全背包
3、01背包
4、后面的等我搞懂了再更...

1、数组递推

上次的文章里面我提到了记忆化搜索,并给出了优化算法,今天我来写一写实际中用得更多的实现方法:数组递推。

//上次问题的数组递推化
f[1] = f[2] = f[3] = 5; f[4] = f[5] = 8; 
for (int i = 6; i <= n; ++i) 
{
 	f[i] = min(f[i - 3] + 5, f[i - 5] + 8);
} 

其实数组递推的方法很简单,我们需要开一个很大的数组,然后按照某种顺序(通常是多重循环)进行转移就行了。相当于将记忆化搜索中的递归进行了展开。

关于数组递推和记忆化搜索的选择:
1、记忆化搜索是自顶向下的,比较符合直觉,不需要考虑转移的顺序,使用的时候比较容易。但是它使用的是递归,缺点是时间复杂度和空间复杂度都会很高,不容易调试。
2、数组递推的优势在于代码简练,常数小,可以进行空间优化等,它的缺点在于需要确定转移顺序,而且只适用于稠密的状态(不然会计算很多稠密的状态)
大部分时候,我们把状态转移方程写出来之后其实数组递推就很好写了,所以我以后数组递推的程序会写的多一点。

2、完全背包

有一个问题描述:考虑有n种物品,第i种物品的每个重量为wi,价值为vi,有无限多个。我们手头有一个大小为m的背包,需要算出能装下的最大总价值。

和昨天的问题有些类似,我们设f(i)表示大小为i的背包最多能装的价值,那么可以得到一个转移方程:f(i) = max{f(i-w1) + v1 , f(i-w2) + v2 , f(i-wn) + vn},如果追求简洁,可以写成:f(i) = max{f(i - wj) + vj},1<=j<i 。初始条件为f(0) = 0

思考一下如何用代码实现:

for(int i = 0 ; i <= m ; ++i)    //容量迭代 
{
	for(int j = 1 ; j <= n ; ++j)   //枚举物品 
	{
		if(i >= w[j]) // 背包当前的容量存得下 
			f[i] = max(f[i] , f[i - w[j]] + v[i]); 
	}
 } 

交换两重循环的顺序也是可以的

for(int i = 1 ; i <= n ; ++i)   //枚举物品
{
	for(int j = 0 ; j <= m ; ++j) //容量迭代
		f[j] = max(f[j] , f[j-w[i]] + v[i]);
} 
 

复杂度分析:我们总共有m个状态,每个状态需要转移n次,故最终的复杂度为O(nm)。

3、01背包

将问题稍作改动:考虑有n种物品,第i种物品的重量为wi,价值为vi,每种物品只有一件。有一个大小为m的背包,需要算出能装下的最大总价值。

问题分析:我们不能再像刚刚那样设计状态了,因为每个物品取过之后就不能再取,所以状态还需要记录物品的相关信息。

考虑如何将问题转化为规模更小的子问题,对于某个物品,再最终的方案中要么取,要么不取,于是我们对这两种情况来分类讨论,转化为子问题:
1、如果没有取第n个物品,那么相当于只有前n-1个物品,背包大小相同的子问题
2、如果取了第n个物品,那么相当于只有前n-1个问题,背包大小减去wn的子问题,再在他的答案上再加上vn的价值。
在两种情况中取价值更高的,得到答案。

那么我们的状态转移方程就已经很好写了:

设f(i,j)表示使用编号为1~n的物品,背包容量为j时的最大值,有转移方程:f(i , j) = max{f(i - 1 , j) , f(i - 1 , j - wi) + vi }
初始条件为:f(0,*) = 0; 代码实现如下:

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

时间复杂度为O(nm)。这段代码的空间复杂度也达到了O(nm),在一些问题中无法接受,我们尝试来优化它。

滚动数组:看刚才的代码我们可以知道,每个f[i][j]在转移的时候只用到了f[i-1][*]。也就是说比i-1更小的再也不会被用到 。如果把f看成一张二维的表格,那么只有两行的格子时活跃的,基于这一思想,我么可以只保存这两行,具体实现如下:

int p = 1, q = 0; 
for (int i = 1; i <= n; ++i) 
{
	 for (int j = 0; j <= m; ++j) 
	{
		 if (j < w[i]) f[p][j] = f[q][j];
		 else f[p][j] = max(f[q][j], f[q][j - w[i]] + v[i]); 
	}
	
	swap(p, q); 
}

继续刚才的思路:把f看成一张二维的表格,那么每个格子在转移时 只会用到上一行中在它左侧的格子。如果我们调整一下转移的顺序,每 一行从右往左进行更新(j从大到小),那么“活跃”的格子就正好只有 上一行的左半部分以及这一行的右半部分。那么实际上我们只需要保存这些活跃的格子的状态就行了。

for (int i = 1; i <= n; ++i) 
{ 
	for (int j = m; j >= w[i]; --j) 
	{ // 倒序,倒序,倒序 
		f[j] = max(f[j], f[j - w[i]] + v[i]); 
	} 
}

以上就是01背包的所有内容了,我的课程设计有一个题目选了01背包的问题,下面我来好好分析一下:(题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2546

读懂题意之后就可以开始将它转换成已知问题了,首先如果想要卡上的余额最少,使用贪心的思想就是将最后的5块钱取购买最贵的物品,所以我们就可以将它转换为容量是余额-5,菜的种类为n-1的01背包问题。

首先我们要列出状态方程:f(i , j) = max{f(i - 1 , j) , f(i - 1)(j - p[i]) + p[i]};
有了状态转移方程之后,我们写代码就很有底气了,我写的代码如下,供大家交流学习。

//留下5块钱去买最贵的菜,则菜数变成 n - 1 , 卡上的余额为m - 5 转换成01背包问题 
//状态转移方程:f(n, m) = max{f(n - 1, m) , f(n - 1 , m - p[n]) +  p[n]}
  
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int p[1005];
int f[1005][1005];


int main()
{
 
	int i , j , m , n;
	while(scanf("%d" , &n) && n) //对于读入正确的每组数据:
	{
		for(i = 1 ; i <= n ; ++i)
			cin >> p[i];
	
		sort(p + 1 ,p + n + 1);   //为了找到最大值 p[n-1]即为价格最大的菜 
	
		cin >> m;
		
		for(i = 0 ; i <= m-5 ; i++)   //初始化条件 , 不然可能影响下组数据 
			f[0][i] = 0;
		
		if(m < 5)  
			cout << m << endl;    //钱数少于5啥也买不了 
		
		else
		{
			for(i = 1 ; i <= n - 1 ; ++i) //01背包的模板代码
			{
				for(j = 0 ; j <= m - 5 ; ++j)
				{
					if(j < p[i])  
						f[i][j] = f[i-1][j]; //选不了
					else 
						f[i][j] = max(f[i-1][j] , f[i-1][j-p[i]] + p[i]);   
				}
			}
	
			cout<<m - f[n-1][m-5] - p[n]<<endl;	
		}
		
	}
	return 0;
} 

立志成为一名攻城狮
最后更新于 2020-03-11