百练oj 2773 采药 01背包

缘起

背包是算法中比较重要的一个主题——各种背包. 从最简单的01背包开始. 百练oj 2773 采药

分析

题目是中文的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
总时间限制: 1000ms 内存限制: 65536kB

描述
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入
输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例输入
70 3
71 100
69 1
1 2

样例输出
3

来源
NOIP 2005

解决这道题之前，我们先来看看什么是01背包问题

01背包问题

1
2
3
01背包问题
有N件物品和一个容量为V 的背包。放入第i件物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使
价值总和最大。

01背包是最基本的背包姿势. 特点是每种物品只有一件，你只有放与不放两种选择.

假设 dp(i,v)是前i件物品放入一个容量为v的背包中所能获得的最大价值. 则显然有如下dp方程

1
dp(i,v) = max{dp(i-1,v), dp(i-1, v-ci)+wi}, 1<=i<=N, ci<=v<=V

即不放(ci,wi)与放(ci,wi)之间取大

于是根据此dp转移方程（物品件数显然是最外层的dp），我们可以给出如下伪代码

1
2
3
4
5
6
7
8
dp(0, 0...V) = 0 // 不放任何一件物品,管你背包容量多大, 价值都是0
for(i=1...N)
{
	for(v=V,...,ci) // [0,...,ci) 范围的dp值不变（因为没得选——肯定放不下ci这件物品啊）,注意,dp的顺序是从V变动到ci, 即从大变小, 而不能从小到大，想想是不难理解的，因为dp是i大的这一层基于i小的这一层进行dp, 如果小的先变化了,则大的就不是基于i小的一层变化了
	{
		dp(i,v) = max{dp(i-1, v), dp(i-1, v-ci)+wi};
	}
}

显然，使用滚动数组可以优化空间复杂度

1
2
3
4
5
6
7
8
dp[0,...,V]=0
for(i = 1,...,N)
{
    for(v = V, .., ci)
    {
        dp(v) = max{dp(v), dp(v-ci)+wi};
    }
}

注意到上面的伪代码中, 第一层循环的参数i在内层循环中是没有用到的（只在ci和wi用到了）, 所以完全可以将它封装起来

1
2
3
4
5
6
7
void zo(c,w)
{
	for(v=V,...,c)
	{
		dp(v) = max{dp(v), dp(v-c)+w}
	}
}

则01背包的伪代码可以写成

1
2
dp(0,...,V)=0
for(i=1,...,N) zo(ci, wi)

关于01背包初始化的细节

如果要求恰好装满背包和不要求恰好装满背包初始化值是不一样的. 前者要求

dp[0,…,V] = {0,-INF,-INF,….,-INF}

后者要求

dp[0,…,V]=0

这是因为dp的意义不一样. 前者dp的意义是合法状态（即恰好装满背包）下的最优值. 后者dp的意义也是合法状态下的最优值，但是后者合法状态和前者合法状态的定义不一样. 所以前者初始化状态中除了容量为0为合法状态之外，都是-INF

01背包的一个常数优化

对于V超大，而物品Wi并不大的情况下，zo方法中的循环常数可以优化为

1
2
3
4
5
6
7
for i = 1 to N
{
	for v = V to max(V − ΣCj(i<=j<=N); Ci) // 这里变化了
	{
		dp(v) = max(dp(v), dp(v-ci)+wi)
	}
}

上面的优化针对于V超大的情况, 如果wi相对不大的话, 则可以节省很多内层循环. 当然其实大部分题目不会卡这里（因为得不偿失嘛~ 你还要去维护部分和）.

为什么上面的优化对呢? 其实内层循环是针对放与不放(ci,wi)这件物品来说的. 那么其实对于两种情况是不需要考虑放与不放的

  1. 背包容量v太小（v<Ci）导致根本想都别想去放置(ci,wi)这件物品，对于这种情况是不需要dp的（因为肯定不能放置(ci,wi)嘛~）, 保持原值即可.
  2. 背包容量v太小（$v+\Sigma_{i<=j<=n}c_i\lt V$），小到足以放置后面所有（(ci,wi),…,(cn,wn)）物品，对于这种情况也是不需要进行dp的. 因为肯定是放置(ci,wi)嘛 ~ 不是说它不会变化，而是得到dp(V)最终的值不需要dp(v)状态的值.

显然，01背包的时间复杂度是O(N*V), 空间复杂度是O(V)

好了 01背包问题介绍到此，至于本题，时间看成ci, 草药的价值看成wi即可，01背包裸题

综上，我们给出本题的ac代码

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
28
29
30
31
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
#define MAX(a,b) ((a)>(b)?(a):(b))

int V,N,dp[1005];

void zo(int c, int w)
{
	for (int v = V; v>=c; v--)
	{
		dp[v] = MAX(dp[v],dp[v-c]+w);
	}
}

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &V, &N);
	for (int i = 1,c,w; i<=N; i++)
	{
		scanf("%d%d", &c, &w);
		zo(c,w);
	}
	printf("%d\n",dp[V]);
	return 0;
}

ac情况

影法师 Accepted 200kB 8ms 449 B G++ 刚刚