代码如下:
# include <iostream>
using namespace std;
int dp[10010], w[200], c[200];
int main()
{
int m, n;
cin>>m>>n;
for(int i = 1; i <= n; i++)
{
cin>>w[i]>>c[i];
}
for(int i = 1; i <= n; i++)
{
for(int j = m; j >= w[i]; j--)
{
dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
}
}
cout<<dp[m]<<endl;
return 0;
}
这个代码能够优化到一维的数组,因为你可以这样理解,就是二维数组的每一行,全部把他放到一行里面去,也就是下面这个转换
至于说一维dp问题,里面有很许多要注意的细节,与二维dp做比较,有很多问题,以下我一一列举下来,我也一一给出答案。
第一个问题:
问:为什么二维背包的遍历顺序背包或者物品重量都可以调换,而优化后一维dp的遍历顺序一定要先是物品然后才是背包?
答案:因为二维背包先遍历物品或者先遍历背包都是可以的,因为后面的结果都是基于行和列来算出的结果。一维dp只能先遍历物品,在遍历背包,因为你不能动每一列的顺序,只能把行往后面加,然后变成了一维dp,然后你遍历的每一个数组,也就是原先每一行的背包容量,所以只能先遍历物品,然后遍历背包。
第二个问题:
问:为什么一维dp遍历背包顺序必须是从后往前遍历,而不是从前往后遍历
假设一组数据
背包容量为4
物品1 重量1 价值15
物品2 重量3 价值20
物品3 重量4 价值30
答:因为我们可以用枚举法,当我们从前往后遍历的话,dp[j] = max(dp[j], dp[j - w[i]] + c[i]);当背包容量为0时,那就是不能放,当背包为1时,最大的就是15,当背包为2时,这个时候还能去放一个物品1,这个时候就重复了,因为物品1只有1个,所以就互相矛盾,只能从后往前遍历了。
第三个问题:
问:为什么遍历顺序是从1开始的?
答:这个也很好理解,因为当0的时候,我们其实就可以默认为没有背包,所以就得从1开始。
总结:其实01背包是最基本的背包问题,我们一定要吃透这个背包问题,才能往后走的更远,打好基础,才能把船行驶的更远。就我而言,我比较笨,我这个问题,我反复学了不下3遍,现在才学好关于这个01背包问题。
标签:遍历,int,1267,9.11,01,一维,物品,背包,dp From: https://blog.csdn.net/Ricky_youngone/article/details/142455725