参考链接：https://blog.csdn.net/bangbanggangan/article/details/81087387

问题

假设编号分别为a,b,c,d,e的五件物品，重量分别是2,2,6,5,4，价值分别是6,3,5,4,6，现在有一个承重为10的背包，如何装入物品具有最大价值？

关键思路：

将问题分解为放入物品a与不放入物品a两种情况的最大值，并推广到所有的物品

流程

  • 建立一个表
    行为当前在这个重量下的最大值
    如第三行则为：当现在有物体0 1 2时，在不同背包最大容量时获得的最大值
    列则为不同重量在不同物体的情况下拥有的最大值
    图片说明

  • 第一行：在背包重量为0时，不可能装下物体0，则此时最大值为0，一直往右走，到达重量2时，可以装下当前的物体，则为6。在此次循环中只有一个物体0，则往后的格子都是6。
    第一行公式为：f（0，j）=0；（j<2）,f(0,j)=6(即w[0]) (j>=2)

  • 第二行：在0和1重量，依旧为0，w为2时，可以装入0或者1，但是由于0的价值比较大，所以装入0，到达4之后，因为可以同时装下0和1，因此为9，之后同样也是。

  • 推广到别的行的话，其中的原理就是：
    f（i，j）=0，（j<w[0]）
    f(i,j)=v[i],(i=0)
    f(i,j)=max(f(i-1,j),f(f(i-1,j-w[i])+v[i]) (j>w[0],i>0)

function knapsack(weights, values, w){
    var n = weights.length -1;//获取物品个数
    var f=[[]];//定义f的矩阵，二维矩阵
    //遍历第一行的内容
    for(var j=0;j<=w;j++){
        //前面第一个物品都装不下的时候
        if(j<weights[0]){//容量当不下物品0的重量，价值为0
        f[0][j]=0;
        }else{
            f[0][j]=values[0];//否则容量为物品0的价值
            }
        }
    //从第二行开始遍历列
    for(var j=0;j<=w;j++){
        //第二行
        for(var i=1;i<=n;i++){
            if(!f[i]){//创建新的一行
                f[i]=[];
            }
            //装不下当前元素的重量时，先为前面的最优值
            if(j<weights[i]){//等于之前的最优值
                f[i][j]=f[i-1][j];
            }else{
                //判断是否装入当前元素
                f[i][j]=Math.max(f[i-1][j],f[i-1][j-weights[i]]+values[i]);
                }
            }
        }
    return f[n][w];
}