01背包整理

常规
1

01背包是一种dp，相对于搜索来说时间更短，所以当数据>50搜索用不了时可以用01背包。
01背包的原理是用之前的局部最优解去算出整体最优解。

例：
有四件物品，体积分别为6、1、5、4，价值分别为50、15、40、25，但你只能拿总体积为10的物品，想要总价值最大，并输出这个总价值。

我们试着用贪心做这道题：体积为6的物品单位价值最高，先选；再选体积为4的物品，总价值为750。
但还有一个更好的方案：拿体积为1、5、4的物品，总价值为800。
这个时候贪心策略错误了，我们需要用01背包来算出结果

✧二维：
f[i][j]表示在考虑前i个物品的情况下，空间为j的最大价值¬
考虑新的物品时，可以从背包容量放得下这个物品时的价值和上一个物品容量为当前容量的价值取最大值
于是就有了状态转移方程：f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + c[i]);

外层枚举种类，内层枚举容量，装不下就直接继承上面的价值：

for(int i = 1; i <= n; i++)
{
	for(int j = 1; j <= m; j++)
	{
		if (j >= w[i])//判断是否装下
		{
			f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + c[i]);
		}
		else
		{
			f[i][j] = f[i - 1][j];
		}
	}
}
cout << f[n][m];//输出最后的值

✧一维：

当数据太大时，例如：
1<=N<=3402,1<=M<=12880,1<=Wi<=400,1<=Di<=100
用二维会变成这样——
image
《美丽的紫色》
于是我们得压缩成一维
我们发现在i-1以前的数据都用不到，所以我们可以使用滚动数组来节省空间
状态转移方程：f[j] = max(f[j - w[i]] + c[i], f[j]);
考虑到之前的值会影响后面的值，所以需要倒着枚举

for(int i = 1; i <= n; i++)
{
	for(int j = m; j >= w[i]; j--)
	{
		f[j] = max(f[j - w[i]] + c[i], f[j]);
	}
}
cout << f[m];
1 个赞