背包的思想:
背包运用的是动态规划的思想,了解的朋友可以跳过下面的一段,又或者你看不懂我下面的概述,也可以去查一查什么是动态规划思想。而且,背包问题在算法的前期只需要掌握这几个就够了。
背包所运用的动态规划思想,动态规划,字面意思,也就是动态地规划局部最优解,最后由局部最优解综合求出答案。简单点来说就是挑选出一个部分,然后枚举每一种方案,在这个部分中求取题目所规定的最优解作为局部最优解,再在局部最优解中挑选出一些组成下一部分的最优解(比如说有n种货物,每种货物有m个,每个货物有w重量与v价值,最多拿重量为k的物品,那我们就可以把这堆货物规划成n个部分,每个部分包含了挑选前i个货物的所有情况,在这里面一层一层递进求解答案。注意:每一个部分根据我上面所说的,都是由前面部分的局部最优解推过来的),以此类推,直至找到答案。
01背包:
01背包含义解释:
注:01背包,是所有背包的核心,只要掌握了它,之后的完全背包及多重背包也就迎刃而解了,所以一定要仔细学习,我也会说得细致一点。
01背包,顾名思义,每种物品只有两种情况,选与不选。一道经典的1背包题就是:有n种货物,每种货物有1个,每个货物有w重量与v价值,最多拿重量为k的物品。也不要觉得后面的完全背包与多重背包有多难,其实就是01背包的变种。
例题:
题目描述
有一个背包容量为m,还有n件物品,它们的重量分别是w1,w2...wn,它们的价值分别为v1,v2...vn,求最大总价值。
输入格式
第一行:两个整数,m(背包容量,m<=200)和n(物品数量,n<=31)
第2~n+1行:每行两个整数wi,vi,表示每个物品的重量和价值。
输出格式
仅一行,一个数,表示最大总价值。
输入样例
输出样例
代码&注释:
代码1:
未优化
编译器食用更佳
代码2:
已优化
**这里的优化的话,我觉得有必要提一嘴,这里优化是减少了一维存物品总量空间,为什么可以这么做呢?因为从代码里我们可以得知,所有的转移都是从前一层转移过来的,且是在j的左边:j-w[i])从这里我们可以发现,之前的很多空间是浪费了的,那如何改变呢?我们不妨仔细想想为什么数据要从前一层转移过来,而不是直接使用这一层的数据呢?不就是为了不让这一层之前产生的数据迭代影响到当前的数据迭代,产生多获取物品的情况吗,如果究其原因,也是因为当循环到dp[j-w[i]]时,dp[j-w[i]]早已在这一层循环产生了改变。同时,我们再来看代码可以得知,同一层内数据改变的会在j的左边产生并被参与到同层的数据迭代只是因为j的循环方向是从左往右的!
**