1. 01背包算法回顾

在上一课中，我们学习了基于动态规划的方法来计算 $n$ 个物品，空间容量为 v 的最大价值问题。在计算过程中，就是基于表格化的方法去推演和记录 dp[i][j]，推演的公式（术语上称为 状态转移方程）为：

dp[i][j] = max(dp[i-1][j-$w_i$]+$p_i$, dp[i-1][j])

这个方法充分体现了 动态规划算法 的精髓思想：

1. 把一个大的、复杂的问题切割成小规模的、相对简单的问题。

例如，有 100 个物品，背包容量是 3000 ，我们为了得出最大值 (dp[100][3000])，那我就先回答 dp[99][3000]，而为了解决 dp[99][3000] 是什么，那我就先解决 dp[98][3000]，是什么......显然，到了 dp[1][$j$] 的时候，这个问题非常简单。

缩小问题的规模，并不改变问题的性质，这是动态规划算法的第一个核心。

2. 表格化记录中间结果，在计算更大规模的问题的时候利用之前记录下来的结果避免了重复计算。

我二维数组来记录 dp[$i$][$j$]，要用到更小规模问题的答案的时候，直接从数组里面查找。

回忆一下我们以前学的 攀天梯 的问题，一个是递归算法，一个是递推算法，递归算法有很多重复的计算，所以效率很低的，很容易超时。（我们还专门为了这个问题学习了 记忆化递归，这是递归算法的一个改进），先算小规模问题，把小规模问题的计算结果表格化记录下来，然后推算大规模问题的答案，这是递归算法的第二个核心。

2. 01背包算法的局限性

我们说过，01枚举 算法的缺点是枚举的次数太多了，如果有 100个物品，每个物品都可以放可以不放，那么总的方案数就是 $2^{100}$ , 这是一个天文数字。

01背包算法 同样有它的局限性。我们可以看到，要回答最后的 $n$ 个物品 ，背包容量为 $v$ 的问题，那就要把 dp数组 $n*v$ 个格子全部填完。如果 $n$ 很大（物品很多），$v$ 很大（背包容量很大），那么这个算法效率就会降低。

可以通过一维数组压缩算法来改善 01背包 算法的空间复杂度。

在上图中，我们进行第 2 轮递推（$i=2，w_2=3, p_2=4$），当 $j=4$ 的时候，把第 2 个物品放入背包能产生最大值，dp[2][4] 被更新（我们是基于那两个绿色框的格子去做 max 运算，填入红色框格子当中）。然后在 $j=7$ 的时候，也是放入第 2 个物品可以产生最大价值，同样是基于 2 蓝色框的格子推算出结果填入红色框格子。

如果还是基于之前的递推顺序，把上面的格子变成一维数组，显然是不可行的。因为在第 4 列的格子变化之后还要用于计算第 7 列的格子，而因为之前的更新而导致后面算第 7 个格子的时候就不对了。

但是，我们也发现一个情况，我们更新的列是在右方，如果我们从右到左推算这个格子，就可以完美的避开了问题。下图是 $i=2$ 的时候的递推过程，最上方是初始状态（也就是 $i=1$ 递推完之后的情况），然后 $j$ 从 $v$ 枚举到 0，也就是说从右到左依次刷新一维数组的内容。

dp[j] = max(dp[$j-w_2$]+$p_2$,dp[$j$])

即便 dp[j] 的值发生了变化，但是在本轮后续的计算中已经不在需要用到，因此数据的正确性能得到保证。

下图为当 $i=2$ (计算第二个物品时) 的一维递推过程，红色框框为循环 $j$ 的时候的计算位置，通过上面的状态转移方程来确定是否放入物品 2 。

3. 例题

题目描述

给定一个容量为 $C$ 的背包，$n$ 个体积分别为 $w_1$, $w_2$, ... , $w_n$ ​的物品，物品 i 放入背包能产生 $p_i$ ​的价值 ( $i = 1 , 2 , ... , n$ , $p_i \lt 0$ , $w_1 \gt 0$)。

每个物品要么整个放入背包，要么不放。放入物品的总体积不能超过背包的总容量 C 。

要求找出最大价值的装包方案。

输入格式

第一行包含两个正整数 $n$ 和 $C$ ( $1 \le n \le 1000$ ，$1 \le C \le 30000$ )

第二行含 $n$ 个正整数 $w_i$ 分别表示 $n$ 个物品的体积 ( $1 \le w_i \le C$ )。

第三行含 $n$ 个正整数 $p_i$ 分别表示 $n$ 个物品放入背包能产生的价值( $1 \le p_i \le 1000$ )。

输出格式

一个整数，代表最大价值。

样例

4 9
2 3 4 5
3 4 5 7

12

程序填空

#include<bits/stdc++.h>
using namespace std;
int dp[填空(1)];
int w[1001],p[1001];
int main()
{
	int n,c;
	
	scanf("%d%d",&n,&c);
	
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);

	for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);

	for(int i=1;i<=n;i++)
	{
		for(int j=c;j>=填空(2);j--) //这一部分空间很小，不可能放入第 i 个物品
			dp[j] = max( 填空(3) , dp[j]);		 
	}
	
	cout<<填空(4);

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}