01背包+滚动数组

2022/7/11 23:21:09

本文主要是介绍01背包+滚动数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

01背包

定义:在\(M\)件物品取出若干件放在空间为\(V\)的背包里,每件物品的体积为\(V_1\),\(V_2\)至\(V_n\),与之相对应的价值为\(W_1\),\(W_2\)至\(W_n\)。

01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。

在01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。

(故称为01背包。)

解决这个问题我们需要从前一个状态递推到下一个状态,最终递推到我们想要的状态。

01背包题目的雏形是:

有\(N\)件物品和一个容量为\(V\)的背包。第\(i\)件物品的体积是\(c[i]\),价值是\(w[i]\)。求解将哪些物品装入背包可使价值总和最大。

这个问题核心的矛盾有两处:1.背包的容量,2.所装物品的价值。

所以,我们不妨假设背包内物品的价值为$ F(I,C)$ 。($ I \(是对应的物品序号,\)C$是它的体积)

阶段:前 \(I\) 件物品中,已经选取若干件物品放在背包中

状态:前 $ I $ 件物品,选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值

决策:第 $ I $ 件物品放或者不放

由此,其状态转移方程为:

\(f[i][v] = max({f[i-1][v],f[i-1][v-c[i]]+w[i]})\)

理解:对于第 \(i\) 件物品,要么不放背包:\(f[i-1][v]\);要么就放入背包:\(f[i-1][v-c[i]]+w[i]\)。

(放入背包,就是 \(-c[i]\) 的体积,然后价值 \(+w[i]\) 。)

代码如下:

void DP(int v,int m)//m个物品,背包体积为v
{
	f[0][0]=0;
	for(int i=1;i<=m;++i)
		for(int j=0;j<=v;++j)	
		{
			f[i][j]=f[i-1][j];
			if(j>=c[i])
				f[i][j]=max(f[i][j],f[i-1][j-c[i]]+w[i]);
		}
}

优化:滚动素组

滚动数组是一种能够在动态规划中降低空间复杂度的方法。

有时某些二维dp方程可以直接降阶到一维,在某些题目中甚至可以降低时间复杂度,是一种极为巧妙的思想。

简要来说,就是通过观察dp方程来判断需要使用哪些数据,可以抛弃哪些数据。

一旦找到关系,就可以用新的数据不断覆盖旧的数据量来减少空间的使用

从而实现“滚动”。

例:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[4];	scanf("%d",&n);//a[0]不用 
	a[1]=1; a[2]=1;
    for(int i=1;i<=n;++i)
    {
        a[3] = a[1] + a[2];
		printf("%d ",a[1]); 
        a[1] = a[2];
        a[2] = a[3];
    }
    return 0;
}
//输入n,得到前n项斐波那契数列。

让$ a_1 $ , $ a_2 $不断的更新迭代,从而完成斐波那契数列的计算。

在01背包中,问题核心的矛盾有两处:1.背包的容量,2.所装物品的价值。

那么对于物品的序号\(i\),便是一个可以抛弃的数据。

我们让$ f[i]\(的数据,覆盖在\)f[i-1]$上。

(就是表格法只用一层表格。)

这时我们的\(F\)函数只有一个参数\(C\)。

也就是说我们在每次遍历时,背包里面刚开始存的是上一个状态的,核心代码变成了这样:

for(i=1;i<=m;++i)//枚举个数
    for(j=c[i];j<=n;++j)//枚举容量
        f[j] = max(f[j],f[j-c[i]] + w[i]);

像之前那样的思考:

如果$ j < c[i] $ 之前是 \(f[i][j] = f[i-1][j]\),

这里就不考虑 \(f[j]\) ,所以 \(f[j]\) 将保存上一次的状态,等价于上述的式子。

如果\(j \geq c[i]\),之前是 \(f[i][j] = max(f[i-1][j],f[i-1][j-c[i]] + w[i])\)

现在是 \(f[j] = max(f[j],f[j - c[i]] + w[i])\)

两者都是在考虑\(i-1\)个物品时容量为\(j\)的最大价值,和上一状态要把这个物品放进去这两个状态之间
得到的最大价值。

既然都是等价的,理论上我们应该可以直接套用这个新的板子。

但是,

其实依然存在一些问题,等价但不完全等价,关键点在于循环顺序

试着考虑这样的一个问题,我们考虑 \(j\) 状态和 \(2j\) 状态:

\(j\) 状态的所面临的问题:

f[j] = max(f[j],f[j-c[i]] + w[i]);

\(2j\) 状态所面临的问题:

f[2j] = max(f[2j],f[2j-c[i]] + w[i]);

当 \(j=c[i]\) 时我们可以看到:

f[j] = max(f[j],f[0] + w[i]);
f[2j] = max(f[2j],f[j] + w[i]);
//j=c[i];
//j-c[i]=0;
//2j-c[i]=j;

对于同一个物品\(c[i]\),在循环到\(j=c[i]\)和\(2j\)时都要考虑放与不放的问题,

所以我们可能在$ f[j]\(时已经把这个物品放进去了,但是在\)f[2j]$时我们又放了一次,

这就违背了题目中每个物品只有一件的题意。

问题出在哪里?

理论上难道不是等价的吗?

其实我们可以发现\(f[2j] = max(f[2j],f[j] + w[i])\)

这里的\(f[j]\)如果已经被更新过,那么它保存的就是这个状态,而不是上一个状态

真正的优化:

所以我们重新考虑循环的顺序,我们采用倒序循环,也就是

void DP(int v,int m)//m个物品,背包体积为v
{
    for(int i=1;i<=m;++i)
        for(int j=v;j>=c[i];--j)
            f[j]=max(f[j],f[j-c[i]]+w[i]);
}

这样我们就可以保证\(max\)中比较的状态都是上一个状态。



这篇关于01背包+滚动数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程