poj3624 0-1背包问题

时间：2021-07-01 04:29:26

问题描述:

Description     POJ3624

问题分析：

N 个物品每个物品有价值v[i]，重量w[i]， 给定背包最大承重M，求背包能够装载的最大价值。每个物品只有放入背包和不放入背包两种选择。

这是典型的0-1背包问题。

定义：

f[n][m] : 给定背包承重m,和n件物品，背包能装载的最大价值。

推导：

f[n][m] =   f[n - 1][m - w[n]] + v[n]  第n件物品放入背包

f[n][m] =   f[n - 1][m]                       第n件物品不放入背包 

f[n][m] 的子问题根据条件会有两个，子问题的选择就比较简单了，两个子问题中求值最大的就是该问题的解。而且根据对于推导式的观察，空间复杂度可以降低。O(m * n)的复杂度可以降低到O(m)。

举例：

索引 1 2 3 4
重量 1 2 3 2
价值 4 6 12 7

计算矩阵：

0 0 0 0 0 0 0
0 4 4 4 4 4 4
0 4 6 10 10 10 10
0 4 6 12 16 18 22
0 4 7 12 16 19 23 

#include<iostream>
#include<fstream>

using namespace std;

static const int N = 3403;
static const int M = 12881;
static int f[N][M];
static int c[N], v[N];

//#define DEBUG

int main()
{
#ifdef DEBUG
	fstream cin("G:\\book\\algorithms\\acm\\Debug\\dat.txt");
#endif

	int n, m;
	while (cin >> n >> m)
	{
		int i, j;
		for (i = 1; i <= n; i++)
		{
			cin >> c[i] >> v[i];
		}
        memset(f, 0, sizeof f);
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j < c[i]; j++)
				f[i][j] = f[i - 1][j];
			for(j = c[i]; j <= m; j++) /* j's domain */
			{
				if (f[i - 1][j] < f[i - 1][j - c[i]] + v[i])
					f[i][j] = f[i - 1][j - c[i]] + v[i];
				else
					f[i][j] = f[i - 1][j];
			}
		}
		cout << f[n][m] << "\n";
	}

	return 0;
}

POJ3624 以上代码内存超限，待优化。

代码的时间上限是O(nm), 对于每个物品i, 它所要遍历的整数区间都是[ci, m]

优化代码如下，理解递推过程后优化就很简单了。

#include<iostream>
#include<fstream>

using namespace std;

static const int N = 3403;
static const int M = 12881;
static int f[M];
static int c[N], v[N];

//#define DEBUG

int main()
{
#ifdef DEBUG
	fstream cin("G:\\book\\algorithms\\acm\\Debug\\dat.txt");
#endif

	int n, m;
	while (cin >> n >> m)
	{
		int i, j;
		for (i = 1; i <= n; i++)
		{
			cin >> c[i] >> v[i];
		}
        memset(f, 0, sizeof f);
		for (i = 1; i <= n; i++)
		{
			for(j = m; j >= c[i]; j--) /* j's domain */
			{
				if (f[j] < f[j - c[i]] + v[i])
					f[j] = f[j - c[i]] + v[i];
			}
		}
		cout << f[m] << "\n";
	}

	return 0;
}

空间复杂度由O(N*V)减少到O(V)
标签：

相关文章