赞
踩
(1)01背包:往容量为j的背包放入前i个物品,所能获得的最大价值(一个物品只能放入一次)
(2)完全背包:往容量为j的背包放入前i个物品,所能获得的最大价值(一个物品可以放入多次)
(1)完全背包(二维)初始化时,dp[0][j] = Math.floor(j / weight[0]) * value[0]
一维:
(1)01背包:dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
(2)完全背包:dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
二维:
(1)01背包:
放不下:dp[i][j] = dp[i - 1][j]
放得下(放 or 不放):dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
(2)完全背包:
放不下:dp[i][j] = dp[i - 1][j]
放得下(放 or 不放):dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])
一维:
(1)01背包:必须先物品后背包(如果先背包后物品,背包永远只放入一个物品),且背 包倒序遍历(如果正序,一个物品会被放入多次)
(2)完全背包:先物品后背包(反过来也可),正序遍历
二维:
(1)01背包:先物品后背包(反过来也可),正序遍历
(2)完全背包:先物品后背包(反过来也可),正序遍历
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。