💕"Su7"💕
作者：Lvzi
文章主要内容：算法系列–动态规划–背包问题(3)–完全背包介绍
大家好,今天为大家带来的是
算法系列--动态规划--背包问题(3)--完全背包介绍
一.完全背包问题
可以发现完全背包问题和01背包问题还是特比相似的
分析:
完全背包问题是01背包问题的推广,是以01背包问题为基础,两种问题的状态表示是相同的
dp[i][j]:在[1,i]所有物品中,在不超过体积j的前提下,可以实现的最大价值
分析状态转移方程时也是以最后一个位置的状态去划分,分为选/不选nums[i],此处就体现出完全背包问题和01背包问题最大的差别,01背包问题如果选择nums[i],选择的物品的数量只能是1(+w[i]),但是完全背包问题如果选择nums[i],可以选择的数量是任意多个(+n * w[i]),此时的状态是任意多个,这样的状态我们在正则表达式匹配那道问题中已经遇到过,解决思路就是利用数学规律,将任意多个状态使用简单的几个状态表示,具体操作是观察所有状态中不变的量,大胆假设,小心求证!!!
以下是状态转移方程的推导:
dp[i][j] = Max(dp[i-1][j],dp[i][j - nums[i]] + w[i])
初始化
- 根据状态表示分析出不需要初始化
返回值:
dp[n][V]
算法系列--动态规划--背包问题(3)--完全背包介绍（下）https://developer.aliyun.com/article/1480856?spm=a2c6h.13148508.setting.18.352e4f0ecxYhMg
