0-1背包问题

0-1 背包问题是经典的动态规划问题

题目

有n件物品和1个容量为W的背包。每种物品均只有一件，第i 件物品的重量为weights[i]，价值为values[i]，求解将哪些物品装入背包可使价值总和最大。

对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态只是1或0, 此问题称为0-1背包问题。

思路

可以将问题的解设为 f(i, j)，其中 i 为物品件数，j为背包的重量。
尝试画一个矩阵来表示它
// TODO

规律

从中可以总结出来规律
f(i, j)= max {f(i-1, j), f(i-1, j-weights[i])+values[i] }

初始值

取矩阵第一排为初始值，即：
若 j < weights[0] , f(i,j) = 0,
若 j >= weights[0] , f(i,j) = values[0]

代码实现

const pack = (values,weights,W)=>{
    let arr = [[]] 
    for(let j=0; j<=W; j++){
        arr[0].push(weights[0]>j ? 0: values[0])
    }
    for(let i=1; i<values.length; i++){
        let tempArr = []
        for(let j=0; j<=W; j++){
            tempArr.push(
                Math.max(
                    arr[i-1][j],
                    j - weights[i] >= 0? arr[i-1][j-weights[i]] + values[i] : 0
                )
            )
        }
        arr.push(tempArr)
    }
    return arr
}

const result = pack([1,2,3,4,5],[1,2,3,4,5],10)

console.log(result)

动态规划三个步骤

• 最优值函数
• 状态转移方程
• 边界条件

拓展-完全背包问题

有n件物品和1个容量为W的背包。每种物品没有上限，第i件物品的重量为weights[i]，价值为values[i]，求解将哪些物品装入背包可使价值总和最大。

拓展-多重背包问题

有n件物品和1个容量为W的背包。每种物品最多number[i]件可用，第i件物品的重量为weights[i]，价值为values[i]，求解将哪些物品装入背包可使价值总和最大。

参考

https://segmentfault.com/a/1190000012829866