哈喽,大家好,今天我给大家带来动态规划中的背包知识点。
> 点个赞吧!!!
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前言
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本蒟蒻是一位只有六年级的小学生,第一次写知识点类型的文章,希望各位大佬多多指点。(点个赞吧!!QVQ)
@AC君 给个精选、置顶吧!!!写这篇文章把我累成狗了好累啊!!!
好了,话不多说,现在就进入正题!!
目录
> 1——动态规划与背包问题
>
>
> 2——01背包
>
>
> 3——完全背包
>
>
> 4——多重背包
>
>
> 5——01背包
>
>
> 6——总结回顾
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> THE FIRST PART:动态规划与背包问题
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
很多同学在刚开始接触动态规划时都会问:”动态规划是什么??“,我也一样,首先让我们一起来看看动态规划的定义。
动态规划(Dynamic Programming,简称DP)是一种用于解决最优化问题和计数问题的高效算法。
实际上,动态规划就是运用了类似递推的思想,中间通过记录子问题的值从而减少重复计算,提高效率。
注意:能运用动态规划解决的题目需拥有最优子结构与无后效性。
新名词:动态转移方程,即转移(递推)时用到的式子(转移式)。
而今天的知识点——背包,就是动态规划中较为基础的一种类型。
背包,顾名思义,就是往一个像背包一样的容器内装不同体积、不同价值的东西。要使得物品体积总和不超过背包容量的情况下,最多能装多少价值的物品。
背包问题主要有三种类型:01背包、完全背包与多重背包。让我们逐一攻破!
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> THE SECOND PART:01背包
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
首先看一道题目:题目
读完题目,你想到了什么??是贪心?还是搜索?……看看接下来这几种经典错误方法中有没有你的方法:
1、按草药的价值从大到小排序
想法:价值越大,越应该取。
错误样例:
本应输出101(取后两种),但是按照这种方法会输出100 ❌
2、按采药的时间从小到大排序
想法:时间少的划算,能取更多。
错误样例:
本应输出100(取第一种),但是按照这种方法会输出99 ❌
3、按采药的”性价比“从小到大排序
想法:性价比越高(时间/价值),取到的价值肯定最大。
错误样例:
本应输出40(取后两种),但是按照这种方法会输出33 ❌
那么正解到底是什么呢??——没错,就是背包(动态规划)
题目翻译:背包体积为T,草药数量为M,每次输入每株草药的体积t[i]与价值w[i]。
分析与解:我们设一个二维数组DP,DP[I][J]表示在当前考虑前I个物品,且背包容量为J的情况下,所能取到物品的最大价值。
接着,我们利用类似于递推的思想,推演DP[I][J]如何得到:
对于我们遇到的每一个物品,只有选与不选两种情况,
1、不选:则继承上一个物品(即考虑I-1个物品时)在背包容量为J时的最大价值和;
2、选:则继承上一个物品在背包容量为(现在背包容量-现在物品体积)的情况下,加上现在物品价值。
接着取两种情况中的最大值就可以解决这道题了。
由此,我们得到了动态转移方程:DP[I][J]=MAX(DP[I-1][J],DP[I-1][J-T[I]]+W[I])
注:此处如果不理解,可以自己打个表试试看。
CODE_1
接下来我们会发现:只需记录上一轮的情况与这一轮的情况即可,可以用滚动数组优化。
CODE_2
然后我们又发现:既然都能用滚动数组优化,那难道就不能直接优化为一维的吗?
最后,我们就得到了01背包问题的模板:
CODE_3
你学会了吗??
更多习题:题1、题2、题3、题4
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> THE THIRD PART:完全背包
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目
完全背包只有一点与01背包不同,就是每件物品有无数件。
此时,我们只需要将第二重循环改为正序即可。
注:此处若有不理解,可以自行打表尝试,在此我就不多赘述(千万别知道是因为我懒)
那么这道题目也就迎刃而解了。
CODE_1
此处再提供一种思路,请大家自行体会(这个方法可能更好理解)
CODE_2
怎么样?是不是很简单?
更多习题:题1、题2
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> THE FOURTH PART:多重背包
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目
多重背包的不同点在于每件物品都有对应的个数,既不是1个,也不是无数个。
对于这样的问题,我们可以在01背包的基础之上加一重循环,用变量K来枚举每一个物品所取的个数。
那么动态转移方程就是:DP[J]=MAX(DP[J],DP[I-1][J-W[I]*K]+V[I]*K)
CODE_1
但是我们会发现,这道题目的数据较大,这个程序无法通过所有测试点,需要优化。
那如何进行优化呢?我们考虑采用二进制拆分的方式,将这个问题转化为01背包问题,减少遍历次数。
例如一个物品有18件,我们可以将它拆分为价值与重量都为1,2,4,8,3的五件物品,(1+2+4+8+3=18)这样就可以高效地解决这个问题了。
CODE_2
所以我们就得到了多重背包的模板了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> THE FIFTH PART:总结回顾
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1、三种背包的不同点:
01背包:每种物品只有1个,只有选与不选两种情况;
完全背包:每种物品有无数个,需考虑要不要取/要取几个;
多重背包:每种物品有固定的个数,需考虑取几个。
2、三种背包的共同点:
代码都较为固定,基于01背包。
3、三种背包的优化:
01背包:滚动数组、一维优化;
完全背包:滚动数组、一维优化;
多重背包:二进制优化。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
结语
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
好了,本期的分享就到这里,“业精于勤荒于嬉,行成于思毁于随”,希望大家多多刷题,早日AC,越变越强!
最后的最后,大家点个赞吧!!