洛谷【P1048 采药】题解

题目链接

分析：典型的01背包问题，设dp[i][j]为空间（也就是题面中的时间）是j的背包在装前i个物品（草药）所得的最大价值，v[i]为第i个物品的重量（采药的时间），w[i]为第i个物品（草药）的价值，则有：

当j>v[i]时，dp[i][j]=max{dp[i-1][j],dp[i-1][j-v[i]]+w[i]}

当j<=v[i]时，dp[i][j]=dp[i-1][j]

接下来，我们就来详细解析一下我们的前辈是怎样得到这个公式的。（知道的可以跳过）

假设我们现在有这样一组数据：

10 4

3 4

4 7

6 11

8 16

我们需要列一个表格，来模拟dp数组变化的过程。

如果你模拟的没错的话，表格最后会是这样的：

我们发现，dp[i][j]总比上面的dp[i-1][j]多（或相等），这是为什么呢？

因为，dp[i][j]表示的是空间是j的背包在装前i个物品所得的最大价值，少装一个物品（也有可能装的一样）不可能比多装一个物品的价值高。

因为上一行（dp[i-1][j]）已经把能装的都装了，所以我们只需要考虑当前物品是否能装的下当前的背包就可以了。

所以，有了这个神奇的状态转移方程：

当j>v[i]时，f[i][j]=max{f[i-1][j],f[i-1][j-v[i]]+w[i]}

当j<=v[i]时，f[i][j]=f[i-1][j]

ok,说了这么多，终于到了大家期待的代码环节：

献上本蒟蒻的代码：

#include<bits/stdc++.h>

using namespace std;

int main()

{

	int n,m;

	int w[105],v[105],dp[105][1005];

	memset(dp,0,sizeof(dp));

	int i,j;

	scanf("%d %d",&m,&n);

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

	for(i=1;i<=n;i++)

	{

		for(j=0;j<=m;j++)

		{

			if(j<v[i]) dp[i][j]=dp[i-1][j];

			else dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

		}

	}

	printf("%d\n",dp[n][m]);

	return 0;

}

但是------------------

这个代码是能进行空间优化的！（虽然这道题不需要）

考虑到状态转移方程只对上一行（dp[i-1][j]）进行操作，所以我们可以将dp数组从这样：

dp[105][1005]

变成这样：

dp[1005]（详见代码）

这，就是传说中的滚动数组。

当然，优化了空间之后，中间的操作也需要一些特殊的操作。（详见代码）

献上本蒟蒻的滚动数组代码：

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int n,m;

    int w[105],v[105],dp[1005];

    memset(dp,0,sizeof(dp));

    int i,j;

    scanf("%d %d",&m,&n);

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

    for(i=1;i<=n;i++)

        for(j=m;j>=0;j--)

            if(j>=v[i]) dp[j]=max(dp[j-v[i]]+w[i],dp[j]);

    printf("%d\n",dp[m]);

    return 0;

}

评测结果：

不加空间优化：

加滚动数组空间优化：

虽然好像没什么变化

巴特西

洛谷【P1048 采药】题解

最新文章

热门文章