部分背包问题快速查阅及空间优化

问题描述

** 假设我们有n件物品，分别编号为1, 2…n。其中编号为i的物品价值为vi，它的重量为wi。为了简化问题，假定价值和重量都是整数值。现在，假设我们有一个背包，它能够承载的重量是W。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？

部分背包问题快速查阅及空间优化
话不多少直接进入正题

部分背包问题快速查阅及空间优化
温馨提示：每个物体只能放进一次哦

寻找递推关系式，面对当前商品有两种可能性：

第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；

第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝

其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；

由此可以得出递推关系式：

1) j<w(i) V(i,j)=V(i-1,j)

2) j>=w(i) V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝

在此give the code:

/*for (int i = 1; i <= number; i++)//空间优化前
	{
		for (int j = w[i]; j <=capacity; j++)//从w[i]开始
		{
			if (j > w[i])
			{
				dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i]] + v[i] );
			}
		}
	}*/

时间空间复杂度均为O(nV)

时间上几乎无优化但空间上还有
！！！
……
怎么优化的呢？
部分背包问题快速查阅及空间优化
B[j]表示j容量下存放的价值最大量。
为什么j要逆序呢？？

如果j不逆序而采用正序j=0…capacity，如上图所示，当j=8时应该有B(8)=B(8-w(3))+v(3)=B(4)+5，然而此时的B(4)已经在j=4的时候被修改过了，原来的B(4)=4，现在B(4)=5，所以计算得出B(8)=5+5=10，（相当于3号物体放进两次）显然这于正确答案不符合；所以该一维数组后面的值需要前面的值进行运算再改动，如果正序便利，则前面的值将有可能被修改掉从而造成后面数据的错误；相反如果逆序遍历，先修改后面的数据再修改前面的数据，此种情况就不会出错了。

给上代码用于查阅：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 100;//物品最大件数
const int maxv = 1000;//V的上限
int w[maxn], v[maxn];
int dp[maxn];

int  main()				//背包问题
{
	int capacity, number;
	scanf_s("%d", &number);
	scanf_s("%d", &capacity);
	
	
	for (int i = 0; i < number; i++)
	{
		scanf_s("%d", &w[i]);
	}
	for (int i = 0; i < number; i++)
	{
		scanf_s("%d", &v[i]);
	}
	
	for (int i = 0; i <= capacity; i++)
	{
		dp[i] = 0;
	}
	/*for (int i = 1; i <= number; i++)//空间优化前
	{
		for (int j = 1; j <=capacity; j++)
		{
			if (j > w[i])
			{
				dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i]] + v[i] );
			}
		}
	}*/
	for (int i = 1; i <= number; i++)//空间优化后
	{
		for (int j = capacity; j >= 0; j--)
		{
			if (j >= w[i])
			{
				dp[j] = max(dp[j],dp[j - w[i]] + v[i] );
			}
		}
	}

	printf("%d", dp[capacity]);//输出最大能装价值
	return 0;
}

欢迎评论交流????

部分背包问题快速查阅及空间优化

问题描述

相关推荐