动态规划学了一段时间了,dp也做了不少了,但是还是有很多题目就是不会做,可能归根原因就是还是没能一步一步把问题搞透搞懂,所以还是得脚踏实地的练习题目并进行思考,并不是为了刷题而刷题,而是为了搞懂去刷题。今天写一下常见的背包问题,希望以后能做到举一反三,慢慢来吧!
01背包
参考:https://blog.csdn.net/qq_37767455/article/details/99086678
就以这题为例。
首先,这题是一道典型的动态规划题目,肯定是用dp数组去解决,我们先不想什么优化空间,就用最基本的dp去做,对应这题,有number和capacity两个制约条件,要的是价值v最大。
所以,有两维,横坐标是i,代表第i个物品,纵坐标是j,代表空间制约为y。dp【i】【j】就表示当前背包容量为j,前i个物品的最佳组合所对应的价值。
base case是什么呢?dp【0】【..】和dp【..】【0】应该为0,不多解释。
还有,主干其实就是两层for循环,各自从1到终点,然后怎么转移呢?
如果当前i对应的体积,即w【i-1】大于j,那么dp【i】【j】只能等于dp【i-1】【j】;如果小于等于,那么dp【i】【j】还能等于dp【i-1】【j-w【i-1】】+v【i-1】,比较两者的最大值就是dp【i】【j】。
OK,下面我们写代码:
1 | public int maxValue(int n,int cap,int[] w,int[] v){ |
下图是我们得到的dp表,我们怎样根据它去得到最优解的情况呢?
首先,看dp【i】【j】是否等于dp【i-1】【j】,如果等于,说明第i个不含有,递归dp【i-1】【j】
如果不等于,看dp【i】【j】是否等于dp【i-1】【j-w【i-1】】+v【i-1】,等于说明装了第i个商品,则递归dp【i-1】【j-w【i-1】】
直到i为0结束。
1 | int[] isHave = new int[4];//统计是否含有 |
完全背包问题
上面是01背包问题,意思就是我们不能无限使用物品,只能用零次或者一次,还有另外一种背包问题就是完全背包问题,就是物品是无限的。
那么我们思考一下,这种情况下,该这么办?
其实好像差不多,只不过dp【i】【j】的转移方程好像需要换一下了,我们还是先看看上面的:
如果当前i对应的体积,即w【i-1】大于j,那么dp【i】【j】只能等于dp【i-1】【j】;如果小于等于,那么dp【i】【j】还能等于dp【i-1】【j-w【i-1】】+v【i-1】,比较两者的最大值就是dp【i】【j】。
对应完全背包问题,如果w【i-1】大于j,那么dp【i】【j】只能等于dp【i-1】【j】,这个不用变即可;如果小于等于,因为可重复,dp【i】【j】还能等于dp【i】【j-w【i-1】】+v【i-1】,比较两者的最大值就是dp【i】【j】。
1 | public int maxValue(int n,int cap,int[] w,int[] v){ |
背包问题的优化可以参考博客:https://zhuanlan.zhihu.com/p/93857890?utm_source=wechat_session
二维数组是可以优化成一维数组的,但是对于01背包和完全背包,第二层的for循环不一样,重复使用的比如完全背包,从小到大递增即可,但是对于01背包最多只能使用1次的话来说,它需要从大到小往前遍历,否则会影响之前的结果。
这一点我其实还有点迷!