Skip to content

Latest commit

 

History

History
317 lines (277 loc) · 7.4 KB

01背包.md

File metadata and controls

317 lines (277 loc) · 7.4 KB
Raw

01背包

问题描述

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，每件物品数量只有一个，现在给你个承重为10的背包，背包里装入的物品具有最大的价值总和是多少？具有最大价值时，分别是哪些物品在包里？

思路分析

状态转移方程为：

设背包总容量为C，j为当前背包可用容量，i为前i个物品，第i个物品价值为Vi，第i个物品重量Wi。
F[i,j]表示当背包可用容量为j时，在前i个物品中，背包能装下的最大价值，有方程：
F[i,j] = max { F[i−1,j], F[i−1,j−Wi]+Vi } （F[i−1,j] 表示不拿，F[i−1,j−Wi]+Vi 表示拿）

表格为：

i name weight value 0 1 2 3 4 5 6 7 8 9 10
4 a 2 6 0 0 6 6 9 9 12 12 15 15 15
3 b 2 3 0 0 3 3 6 6 9 9 9 10 11
2 c 6 5 0 0 0 0 6 6 6 6 6 10 11
1 d 5 4 0 0 0 0 6 6 6 6 6 10 10
0 e 4 6 0 0 0 0 6 6 6 6 6 6 6

使用一个一维数组res[n]，如果物品i被拿，则res[i] = 1，判断是否被拿的条件如下：

F[i,j]==F[i-1,j-W[i]+V[i]]

我的实现1

/*
*  W：物品重量数组
*  V：物品价值数组
*  res:结果输出，当获取最大重量时，分别是哪几个物品在包中
*  n：物品数量
*  C：背包总容量
*  返回值：背包的最大价值
*/
int Package01(int *W, int *V, int *res, int n, int C)
{
	//表格
	int** F = new int*[n];
	for (int i = 0; i < n; i++)
	{
		F[i] = new int[C + 1];
	}
	//初始化表格
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= C; j++)
			F[i][j] = 0;
	}
	//第1列，表示背包容量为0时，所以第1列都为0
	//初始化第1行，当背包容量小于第1个物品重量时，背包价值为0，否则为背包价值为第1个物品价值
	for (int i = 1; i <= C; i++)
	{
		F[0][i] = (i < W[0]) ? 0 : V[0];
	}
	//i表示物品下标
	for (int i = 1; i < n; i++)
	{
		//j表示背包容量
		for (int j = 1; j <= C; j++)
		{
			if (j < W[i])
			{
				F[i][j] = F[i - 1][j];
			}
			else
			{
				//状态转移方程
				F[i][j] = (F[i - 1][j]>F[i - 1][j - W[i]] + V[i]) ? F[i - 1][j] : F[i - 1][j - W[i]] + V[i];
			}
		}
	}

	int maxValue = F[n - 1][C];
	//下面计算分别都是哪些物品在包中
	int i = n - 1;
	int j = C;
	while (i)
	{
		//bool test = (F[i][j] == F[i - 1][j - W[i]] + V[i]);
		if (F[i][j] == F[i - 1][j - W[i]] + V[i])
		{
			res[i] = 1;
			j = j - W[i];
		}
		i--;
	}
	if (F[0][j])
		res[0] = 1;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= C; j++)
			cout << F[i][j] << " ";
		cout << endl;
	}

	//清理动态分配内存
	for (int i = 0; i < n; i++)
	{
		delete[] F[i];
		F[i] = nullptr;
	}
	delete[] F;
	F = nullptr;
	return maxValue;
}

//处理输入输出
//输入：
//第1行：物品个数n，背包总容量C
//第i(i>=2)行到第(i+n-1)行：物品重量Wi，物品价值Vi
int main()
{
	int n = 0;
	int C = 0;
	cin >> n >> C;
	if (n <= 0 || C <= 0)
		return 0;
	int* W = new int[n];
	int* V = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> W[i] >> V[i];
	}
	int* res = new int[n];
	for (int i = 0; i < n; i++)
		res[i] = 0;
	int maxValue = Package01(W, V, res, n, C);
	for (int i = 0; i < n; i++)
	{
		cout << res[i] << " ";
	}
	cout << endl;
	cout << maxValue << endl;

	delete[] W;
	W = nullptr;
	delete[] V;
	V = nullptr;
	delete[] res;
	res = nullptr;
	system("pause");
	return 0;
}
/*
输入为：
5 10      //5种物品，背包承重为10
2 6       //第一种物品，重量为2，价值为1，数目1个
2 3
6 5
5 4
4 6
输出为：
0 0 6 6 6 6 6 6 6 6 6
0 0 6 6 9 9 9 9 9 9 9
0 0 6 6 9 9 9 9 11 11 14
0 0 6 6 9 9 9 10 11 13 14
0 0 6 6 9 9 12 12 15 15 15
1 1 0 0 1
15
*/

优化

因为在考虑前i个问题时，只与i-1的结果相关，可以使用一维数组来存放结果，又因为F[i,j]需要参考F[i-1,j]和F[i-1,j-Wi]的值，我们可以通过从右到左的遍历，避免数据被覆盖。因此有：

F[j] = max { F[j], F[j−Wi]+Vi } j初始化为背包总容量C

在这种情况，求哪些物品在包中的方法就不可用了，新方法为，使用一二维数组path[][]，当物品计算某一F[j]时，如果物品i被拿了，则标记path[i,j]。但这样貌似又是O(nC)的空间了。：（，如果不用求路径的情况下这种方法更好吧。

我的实现2

int Package01(int *W, int *V, int**path, int n, int C)
{
	int* F = new int[C + 1];
	//初始化第0个物品，即第1行
	for (int j = 0; j <= C; j++)
	{
		if (j < W[0])
			F[j] = 0;
		else
		{
			F[j] = V[0];
			path[0][j] = 1;
		}
			
	}
	//从物品1开始遍历，即第2行
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= C; j++)
			cout << F[j] <<" ";
		cout << endl;
		//逆序遍历
		for (int j = C; j >= 0; j--)
		{
			if (j >= W[i] && F[j - W[i]] + V[i] > F[j])
			{
				F[j] = F[j - W[i]] + V[i];
				path[i][j] = 1;
			}
			
		}
		
	}
	//打印最后一行
	for (int j = 0; j <= C; j++)
		cout << F[j] << " ";
	cout << endl;

	int maxValue = F[C];
	delete[] F;
	return maxValue;
}

int main()
{
	int n = 0;
	int C = 0;
	cin >> n >> C;
	if (n <= 0 || C <= 0)
		return 0;
	int* W = new int[n];
	int* V = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> W[i] >> V[i];
	}
	int** path = new int*[n];
	for (int i = 0; i < n; i++)
		path[i] = new int[C + 1];
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= C; j++)
			path[i][j] = 0;
	}

	int maxValue = Package01(W, V, path, n, C);
	
	cout << maxValue << endl;

	//输出路径
	int i = n - 1;
	int j = C;
	while (i >= 0 && j >= 0)
	{
		if (path[i][j] == 1)
		{
			cout << i << " ";
			j -= W[i];
		}
		i--;
	}
	cout << endl;
	
	delete[] W;
	W = nullptr;
	delete[] V;
	V = nullptr;
	for (int i = 0; i < n; i++)
	{
		delete[] path[i];
		path[i] = nullptr;
	}
	delete[] path;
	path = nullptr;
	return 0;
}
/*
输入：
5 10
2 6
2 3
6 5
5 4
4 6
输出：
0 0 6 6 6 6 6 6 6 6 6
0 0 6 6 9 9 9 9 9 9 9
0 0 6 6 9 9 9 9 11 11 14
0 0 6 6 9 9 9 10 11 13 14
0 0 6 6 9 9 12 12 15 15 15
15
4 1 0
*/

包装满的最优解

如果要求是，包必须装满，那么可以将F方程除F[i][0]之外的格子初始化为负无穷（表示为不合法输出，下面用-%表示），因此有以下矩阵：

i name weight value 0 1 2 3 4 5 6 7 8 9 10
4 a 2 6 0 -% 6 -% 9 4 12 10 15 13 14
3 b 2 3 0 -% 3 -% 6 4 9 7 8 10 11
2 c 6 5 0 -% -% -% 6 4 5 -% -% 10 11
1 d 5 4 0 -% -% -% 6 4 -% -% -% 10 -%
0 e 4 6 0 -% -% -% 6 -% -% -% -% -% -%