背包问题概述动态规划 [复制链接]

写在前

问题描述

有N件物品和一个最多能被重量为W的背包。一个物品只有两个属性：重量和价值。第i件物品的重量是weight，得到的价值是value。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

注意：0-1背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。

基本思路

这里有两个可变量体积和价值，我们定义dp[j]表示前i件物品体积不超过j能达到的最大价值，设第i件物品体积为w，价值为v，根据第i件物品是否添加到背包中，可以分两种情况讨论：

第i件物品没添加到背包，最大价值：dp[j]=dp[i-1][j]。

第i件物品添加到背包中：dp[j]=dp[i-1][j-w]+v。

第i件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1背包的状态转移方程为：

dp[j]=max(dp[i-1][j],dp[i-1][j-w]+v)

代码实现

//W为背包总重量//N为物品数量//weights数组存储N个物品的重量//values数组存储N个物品的价值publicintknapsack(intW,intN,int[]weights,int[]values){//dp[0]和dp[0][j]没有价值已经初始化0int[][]dp=newint[N+1][W+1];//从dp[1][1]开始遍历填表for(inti=1;i=N;++i){//第i件物品的重量和价值intw=weights[i-1],v=values[i-1];for(intj=1;j=W;++j){if(jw){//超过当前状态能装下的重量jdp[j]=dp[i-1][j];}else{dp[j]=Math.max(dp[i-1][j],dp[i-1][j-weights]+values);}}}turndp[N][W];}

dp[j]的值只与dp[i-1][0,...,j-1]有关，所以我们可以采用动态规划常用的方法（滚动数组）对空间进行优化（即去掉dp的第一维）。因此，0-1背包的状态转移方程为：dp[j]=max(dp[j],dp[j-w]+v)

特别注意：为了防止上一层循环的dp[0,...,j-1]被覆盖，循环的时候j只能逆向遍历。优化空间复杂度：

ps:滚动数组：即让数组滚动起来，每次都使用固定的几个存储空间，来达到压缩，节省存储空间的作用。

publicintknapsack(intW,intN,int[]weights,int[]values){int[]dp=newint[W+1];for(inti=1;i=N;i++){intw=weights[i-1],v=values[i-1];for(intj=W;j=1;--j){if(j=w){dp[j]=Math.max(dp[j],dp[j-w]+v);}}}turndp[W];}

ps：01背包内循环理解：还原成二维的dp就很好理解，一维的dp是二维dp在空间上进行复用的结果。dp=f(dp[i-num])，等式的右边其实是二维dp上一行的数据，应该是只读的，在被读取前不应该被修改。如果正序的话，靠后的元素在读取前右边的dp有可能被修改了，倒序可以避免读取前被修改的问题。

转自简书：_code_x原文链接：