0/1背包 – NOIP2005P3

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

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

  • 二维数组表示
    • 定义状态:(fleft [ i right ]left [ c right ])表示前(i)件物品恰放入一个容量为(c)的背包可以获得的最大价值。
    • 状态转移方程:(fleft [ i right ]left [ c right ]=maxleft { fleft [ i-1 right ]left [ c right ],fleft [i-1  right ]left [ c-wleft [ i right ] right ] +vleft [ i right ]right })
    • 代码模版:
      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]); }
      	}
      }
    • 时间复杂度、空间复杂度:(Oleft ( NC right ))
  • 一维数组表示
    • 定义状态:由于(i)基本没有什么用处,所以我们把它省略。
    • 状态转移方程:(fleft [ c right ]=maxleft { fleft [ c right ],fleft [ c-wleft [ i right ] right ] +vleft [ i right ]right })需要注意的是,这时候,我们需要将(c)从(C)开始,倒着推。
    • 代码模版:
      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]); }
      	}
      }
    • 时间复杂度:(Oleft ( NC right ))
    • 空间复杂度:(Oleft ( C right ))
  • 一维数组表示下的常数优化
    • 内层循环的下限不需要为0。
    • 代码模版:
      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]); }
      	}
      }
  • 初始化的细节
    • 若要求“恰好装满”:(fleft [ 0 right ]=0),其他(fleft [ i right ]=textrm{-INF})。
    • 若不用“恰好装满”:(fleft [ 0 right ]=0)。

最后附上NOIP2005P3的代码:

#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;
}

发表评论