算法思想
- 核心思想:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法
- 动态规划算法与分支算法类似,其基本思想也是将求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解得到原问题的解
- 与分治法不同的是,适合用于动态规划求解的问题,经分解得到的子问题往往不是相互独立的。(也就是下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)
- 动态规划往往是通过填表的方式逐步推进,得到最优解
背包问题
背包问题主要是指一个给定容量的背包,若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值最大。其中又分0-1背包问题(指的是:每一个物品只能用一次)和完全背包问题(完全背包是指:每一个物品都有无限件可用)。
- 无限背包问题可以转化为0-1背包问题进行求解
参考:https://blog.csdn.net/weixin_41162823/article/details/87878853
0-1背包问题
问题描述:给定n个物体(它们的重量为:w1,w2,……,wn,价值为:v1,v2,……,vn) 和 一个承受重量为W的背包,问怎么选取这些物体,放在背包中(不超过背包的承重),让所取的子集达到最大价值。
代码实现
1 | package com.data.structure; |
代码实现2
1 | package com.data.structure; |
- 本文作者: 半度微凉
- 本文链接: http://www.taoweidong.com/2020/03/21/Java数据结构和算法-动态规划算法/
- 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!