01背包与广义背包 动态规划求解

背包与广义背包 动态规划求解"/>

01背包与广义背包 动态规划求解

0-1背包动态规划

• 问题描述

  01背包问题的描述如下：给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包1次或不装入（且不能仅装入物品的一部分）。

• 递推公式

• 伪代码

/*
M //最大质量
m //质量数组 下标 1 to n
v //价值数组 下标 1 to n 
时间复杂度 : O(nM)
空间复杂度: O(nM)
*/
zero_one_KP(M,m,v)//initlet n = m.lengthlet dp = [n+1][M] //(n+1)xM 矩阵 下标 [1,n+1] , [1,M]//init end//动态规划for i=1 to n //递增for j = M to m[i] //递减dp[i][j] = max(dp[i-1][j],dp[i-1][j-m[i]]+v[i] )//回溯解let j = Mlet x //解向量for i=n to 1 //递减if dp[i][j] == dp[i-1][j]x[i] = 0elsex[i] = 1j = j- m[i]return dp[n+1][M], x

• 优化

zero_one_KP(M,m,v) //优化后//initlet n = m.lengthlet dp = new Vector //向量下标 1,Mlet path = Map //哈希表//init end//动态规划for i=1 to n //递增for j = M to m[i] //递减let tmp = dp[j-m[i]]+v[i]if dp[j] < tmpdp[j] = tmppath[(i,j)] = 1//回溯解let j = Mlet i = nlet x  //解向量 下标 1 to n, 全部初始化为0while j>0&&i>0if path[(i,j)] ==1x[i] = 1j = j - m[i]i = i-1return dp[M], x

• Javascript实现

//0-1背包问题
function zero_one_KP(M, m, v) {var n = m.length/*M:背包最大承重量n:物品种类个数m:物品质量时间复杂度: O(nM)空间复杂度: O(nM)*/var i, j;var dp = new Array(n + 1)for (i = 0; i <= n; i++) {dp[i] = new Array(M + 1).fill(0)}for (i = 1; i <= n; i++) {for (j = M; j >= m[i - 1]; j--) { //从大到小var tmp = dp[i - 1][j - m[i - 1]] + v[i - 1]dp[i][j] = max(dp[i - 1][j], tmp)}}j = Mvar x = new Array(n).fill(0)for (i = n; i >= 1; i--) {if (dp[i][j] == dp[i - 1][j]) {x[i - 1] = 0} else {x[i - 1] = 1j -= m[i - 1]}}return [dp[n][M], x]
}

• 优化后

//0-1背包问题
function zero_one_KP(M, m, v) {/*M:背包最大承重量n:物品种类个数m:物品质量时间复杂度: O(nM)空间复杂度: O(M)
*/
var n = m.lengthvar i, j;let path = new Map()let f = new Array(M + 1).fill(0)for (i = 1; i <= n; i++) {for (j = M; j >= m[i - 1]; j--) { //从大到小var tmp = f[j - m[i - 1]] + v[i - 1]if (f[j] < tmp) {f[j] = tmppath[[i, j]] = 1}}}j = Mi = nvar x = new Array(n).fill(0)while (i > 0 && j > 0) {if (path[[i, j]] == 1) {x[i - 1] = 1j = j - m[i - 1]}i = i – 1 // 注意这里}return [f[M], x]
}

二.广义背包

问题描述

广义背包问题的描述如下：给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）。

递推公式

伪代码

• 未优化

//init
let dp = (n+1)x(M+1)矩阵
let path = new Map() //哈希表
//init end
for i=1 to nfor j = 0 to Mlet count = j/m[i] //向量 m与v 下标 1 to nfor k=0 to countdp[i][j] = dp[i-1][j]let tmp = dp[i - 1][j - k * m[i]] + k * v[i]if dp[i][j] < tmpdp[i][j] = tmppath[(i,j)] = 1
//解向量
let j = M
let i = n
let x  be a new Vector// 下标范围 [1,n]
while i>0 && j>0if path[(i,j)] ==1x[i]++j = j- m[i]else i = i-1
return dp[n][M] , x  

• 优化1

let dp = (n+1)x(M+1)矩阵
let path = new Map() //哈希表for i=1 to nfor j = 0 to Mdp[i][j] = dp[i-1][j]if j >= m[i-1] && dp[i][j] <dp[i][j-m[i-1]]+v[i-1]dp[i][j] = dp[i][j-m[i-1]]+v[i-1]path[[i,j]] = 1
//解向量
let j = M
let i = n
let x  be a new Vector// 下标范围 [1,n]
while i>0 && j>0if path[(i,j)] ==1x[i]++j = j- m[i]else i = i-1
return dp[n][M] , x

• 优化2

let f //向量 下标 0 to M
let path = new Map() //哈希表for i=1 to nfor j = m[i]  to  M let tmp = f[j - m[i]] + v[i]if f[j] < tmpf[j] = tmppath[[i, j]] = 1
//解向量
let j = M
let i = n
let x  be a new Vector// 下标范围 [1,n]
while i>0 && j>0if path[(i,j)] ==1x[i]++j = j- m[i]else i = i-1
return f[M], x

Javascript实现

• 未优化

function GKP0(M, m, v) {var n = m.length/*M:背包最大承重量n:物品种类个数m:物品质量*/var i, j, k;var dp = new Array(n + 1)for (i = 0; i <= n; i++) {dp[i] = new Array(M + 1).fill(0)}var x = new Array(n + 1).fill(0)var path = {}for (i = 1; i <= n; i++) {for (j = 0; j <= M; j++) {var count = j / m[i - 1]for (k = 0; k <= count; k++) {dp[i][j] = dp[i - 1][j]var tmp = dp[i - 1][j - k * m[i - 1]] + k * v[i - 1]if (dp[i][j] < tmp) {dp[i][j] = tmppath[[i, j]] = 1}}}}//解路径j = Mi = nwhile (i > 0 && j > 0) {if (path[[i, j]] == 1) {x[i - 1]++j = j - m[i - 1]} else {i = i - 1}}x.pop()console.log("解=", x)return [dp[n][M], x]
}

• 优化2

function GKP(M, m, v) {var n = m.lengthvar i, j;var x = {} //解向量 for (i = 0; i <= n; i++) {x[i] = 0}var path = new Map()let f = new Array(M + 1).fill(0)for (i = 1; i <= n; i++) {for (j = m[i - 1]; j <= M; j++) {var tmp = f[j - m[i - 1]] + v[i - 1]if (f[j] < tmp) {f[j] = tmppath[[i, j]] = 1}}}//解路径j = Mi = nwhile (i > 0 && j > 0) {if (path[[i, j]] == 1) {x[i - 1]++j = j - m[i - 1]} else {i = i - 1}}console.log("最少花费 = ", f[M])console.log("解向量 = ", x)return [f[M], x]
}