0/1 背包 - NOIP2005P3

2013-08-23 约 708 字预计阅读 2 分钟

题目是经典的采药问题。也是最基础的 0/1 背包问题。

我们约定有 $ N $ 件物品和一个容量为 $ C $ 的背包。第 $ i $ 件物品的重量是 $ w\left [ i \right ] $ ，价值是 $ v\left [ i \right ] $ 。这样，我们所需要求解将哪些物品装入背包可使价值总和最大。

二维数组表示

定义状态： $ f\left [ i \right ]\left [ c \right ] $ 表示前 $ i $ 件物品恰放入一个容量为 $ c $ 的背包可以获得的最大价值。

状态转移方程： $ f\left [ i \right ]\left [ c \right ]=\max\left \{ f\left [ i-1 \right ]\left [ c \right ],f\left [i-1 \right ]\left [ c-w\left [ i \right ] \right ] +v\left [ i \right ]\right \} $

代码模版：

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= N; i++)
{
	for(int c = 0; c <= C; c++)
	{
		f[i][c] = f[i - 1][c];
		if(c >= w[i])
		{ f[i][c] = max(f[i][c], f[i - 1][c - w[i]] + v[i]); }
	}
}

时间复杂度、空间复杂度： $ O\left ( NC \right ) $

一维数组表示

定义状态：由于 $ i $ 基本没有什么用处，所以我们把它省略。

状态转移方程： $ f\left [ c \right ]=\max\left \{ f\left [ c \right ],f\left [ c-w\left [ i \right ] \right ] +v\left [ i \right ]\right \} $ 需要注意的是，这时候，我们需要将 $ c $ 从 $ C $ 开始，倒着推。

代码模版：

1
2
3
4
5
6
7
8
for(int i = 1; i <= N; i++)
{
	for(int c = C; C >= 0; C--)
	{
		if(c >= w[i])
		{ f[c] = max(f[c], f[c - w[i]] + v[i]); }
	}
}

时间复杂度： $ O\left ( NC \right ) $

空间复杂度： $ O\left ( C \right ) $

一维数组表示下的常数优化

内层循环的下限不需要为 0。

代码模版：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int bound, sumw = 0;
for(int i = 1; i <= N; i++)
{
	sumw += w[i];
	bound = max(C - sumw, w[i]);
	for(int c = C; C >= bound; C--)
	{
		if(c >= w[i])
		{ f[c] = max(f[c], f[c - w[i]] + v[i]); }
	}
}

初始化的细节：

若要求“恰好装满”： $ f\left [ 0 \right ]=0 $ ，其他 $ f\left [ i \right ]=\textrm{-INF} $ 。
若不用“恰好装满”： $ f\left [ 0 \right ]=0 $ 。

最后附上 NOIP2005P3 的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <memory.h>
#include <algorithm>

using namespace std;

const int MAX = 1024;

int C, N;
int pC[MAX], pW[MAX], f[MAX];

int main()
{
	cin >> C >> N;
	for(int i = 0; i < N; i++)
	{ cin >> pC[i] >> pW[i]; }
	memset(f, 0, sizeof(f));
	for(int i = 0; i < N; i++)
	{
		for(int j = C; j >= pC[i]; j--)
		{
			f[j] = max(f[j], f[j - pC[i]] + pW[i]);
		} 
	}
	cout << f[C] << endl;
	return 0;
}

目录

0/1 背包 - NOIP2005P3

二维数组表示

一维数组表示

一维数组表示下的常数优化