猫史档案馆

本教程特别难！前方高能！萌新退避！！！

-------------------------------------------------------------------------

一、我们举个栗子来理解它

假设你是个小偷，被这一个可以装四千克的背包。

你可以喵的商品有3件：

音响       笔记本电脑        吉他

3000元                      2000元                         1500元

 4千克                         3千克                           1千克

为了让喵的商品价值更高，你该选择商品？

方法1

最简单的算法——枚举

就是一个个枚举出来，时间复杂度是O(2^n)，每增加一件商品，所用的时间就会以几何倍喵！真的是慢如蜗牛。

看图！

方法2

动态规划！

这是一种解决棘手问题的方法，它将大问题分成一个个子问题，并先着手解决子问题。

对于01背包问题，你先解决子背包问题，在逐步解决原来的问题。

我们先来演示一下这种算法的执行过程。看完过程后我们再写代码。

每一个动态规划都从一个网格开始：

网格最初是空的，让我们定义一下：i代表行，j代表列，而这个表格就叫dp（动态规划的简写）。

那么dp[i][j]的定义又是什么呢？不急，我们先填满这个网格。

1.吉他行

第一个单元格表示背包的容量为1kg，吉他的重量也是1kg，这意味着它可以装入背包！因此这个单元格包含吉他，价值1500元。

与这个单元格一样，每个单元格都将包含当前可装入背包的所有商品。

别忘了，这是第一行，只有吉他可供你选择。换言而之，你假装现在还没发喵其他两件商品。

2.音响行

我们来填充下一行——音响行。你现在处于第二行，可偷的商品有吉他和音响。在每一行，可偷的商品都为当前行的商品以及之前各行的商品。因此，当前你还不能偷笔记本电脑，而只能偷音响和吉他。我们先来看第一个单元格，它表示容量为1kg的背包。在此之前，可装入1kg背包的商品的最大价值为1500元。

该不该偷音响呢？

不不不！音响太重了！所以还是1500元。

接下来的两个单元格的情况与此相同

现在背包的容量为4kg，终于够装下音响了！原来的最大价值为1500元，但如果在背包中装入音响而不是吉他，价格将为3000元！因此还是偷音响吧。

你更新了最大价值！在这个网格里，你将逐步更新最大价值。

3.笔记本电脑行

下面一同样的方式处理笔记本电脑。笔记本电脑重3kg，没发装入容量为1kg或2kg的背包，因此前两个单元格的最大价值还是1500元，但到了第三个单元格，我们有了一个3kg的背包，可以装下笔记本电脑了，最大价值为2000元。

对于容量为4kg的背包，情况很有趣。这是非常重要的部分。当前最大价值为3000元，你可不偷音响，而偷笔记本电脑只值2000元。

3000 VS 2000

  音响                 笔记本电脑

价值没有原来高。但等一等，笔记本电脑的重量只有3kg，背包还有1kg的容量没用！

3000 VS （2000 + 剩下容量的价值）

     音响                       笔记本电脑                   余下1kg的价值

就是：

3000 VS （2000 + 1500）

     音响                       笔记本电脑              吉他

所以，我们选笔记本电脑和吉他！

最终网格如下：

好了，我们现在来揭晓答案，dp[i][j]的意义是：                         { 1.上一个单元的值（dp[i-1][j]的值） dp[i][j] = max{                       {2.当前商品的价值 + 剩余空间的价值                                                     （dp[i-1][j-当前商品的重量]） 二、上代码 1.kitten 4.0（看不清就放大网页吧，Ctrl+鼠标滚轮）：看起来很繁琐对不对！看不懂就自己写一遍吧，实在不行就在评论区找大佬吧…… 2.C++：

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	int dp[n+1][m+1],weight[n+1],value[n+1];
	for(int i=1;i<=n;++i)
		cin>>weight[i]>>value[i];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			dp[i][j]=dp[i-1][j];
			if(j>=weight[i])dp[i][j]=max(dp[i-1][j],value[i]+dp[i-1][j-weight[i]]);
		}
	}
	cout<<dp[n][m];
    return 0;
}

好了，不是大佬以下的内容就不用看了。

三、空间优化

其实我们可以把二维数组变成一维数组，就是数组滚动！

倒叙遍历是为了保证物品i只被放入一次！但如果一旦正序遍历了，那么物品0就会被重复加入多次！

C++：

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	int dp[m+1],weight[n+1],value[n+1];
	for(int i=1;i<=n;++i)
		cin>>weight[i]>>value[i];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;++i){
		for(int j=m;j>=weight[i];--j)
			dp[j]=max(dp[j],value[i]+dp[j-weight[i]]);
	}
	cout<<dp[m];
    return 0;
}

三、我自己的一点点优化

我们可以在获取输入时输入一个数就计算一次

C++:

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	int dp[m+1],weight[n+1],value[n+1];
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;++i){
		cin>>weight[i]>>value[i];
		for(int j=m;j>=weight[i];--j)
			dp[j]=max(dp[j],value[i]+dp[j-weight[i]]);
	}
	cout<<dp[m];
    return 0;
}

四、最后……

首先发一下AC证明这个帖子的可用性（最上面的是优化后的）：

好了，相信看到这里的你们都很有耐心，听懂了的大佬在评论区扣1。 然后呢，我没写Python和Java的代码，希望有位大佬在评论区补上。 制贴不易，不喜勿喷！（不知道要过几载才会更新第二讲）