动态规划算法js版：01背包问题

最优化原理

一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略

动态规划的核心就是最优化原理

• 01背包问题

状态转移方程

V(i,j) = Max{ V(i-1,j) , V(i-1,j-w(i))+v(i) }

js代码如下

let w = [2,3,4,5]
let v = [3,4,5,6]
console.log(fun(w,v,9))

function fun(w,v,capacity){
    //初始化表格
    let V = new Array(w.length)
    for (let d= 0 ;d<w.length;d++){ V[d] = new Array(capacity)}
    
    for(let i = 0;i<w.length;i++){
        for(let j = 0;j<capacity;j++){
            V[i][j] = Math.max(P(i-1,j),P(i-1,j-w[i])+v[i] )
        }
    }
    
    //表格超出边界值为0
    function P(i,j){return V[i] && V[i][j] || 0 }
    return V[w.length-1][capacity-1]
}

• 完全背包问题(未完)

状态转移方程

V(i) = Max{V(i),V(i-1,j-w(i))+v(j)}

js代码

let w = [2,3,4,5]
let v = [3,4,5,6]
console.log(fun(w,v,9))

function fun(w,v,capacity){
    //初始化表格
    let V = new Array(w.length)
    for(let i = 0;i<w.length;i++){
        for(let j = 0;j<capacity;j++){
            V[j] = Math.max(P(j),P(j-w[i])+v[i] )
        }
    }
    
    //表格超出边界值为0
    function P(i){return V[i] || 0 }
    return V[capacity-1]
}