lintcode125-背包问题

[lxw124]

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值. 问最多能装入背包的总价值是多大? 样例 1:

输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4] 输出: 9 解释: 装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9 样例 2:

输入: m = 10, A = [2, 3, 8], V = [2, 5, 8] 输出: 10 解释: 装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10

[lxw124]

设置一个二维数组，dp[i][j],i为物品大小，j为背包容量，值为价值

const backPackII = function (m, A, V) {
const dp=[]
for(var i=0;i<=A.length;i++){
    dp[i]=[]
    for(var j=0;j<=m;j++){
        if(j==0||i==0){
            dp[i][j]=0;
        }else if(A[i-1]<=j){
            const a=V[i-1]+dp[i-1][j-A[i-1]]
            const b=dp[i-1][j]
            dp[i][j]=a>b?a:b;
        }else{
            dp[i][j]=dp[i-1][j]
        }
    }
}
return dp[A.length][m]
}