01背包

 1 /**
 2  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 3  * 计算01背包问题的结果
 4  * @param V int整型 背包的体积
 5  * @param n int整型 物品的个数
 6  * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
 7  * @return int整型
 8  */
 9 function knapsack( V ,  n ,  vw ) {
10     // write code here
11     if(V === 0 || n === 0 || vw.length === 0){
12         return 0;
13     }
14     const dp = Array.from(new Array(n+1),()=>new Array(V+1).fill(0));
15     for(let i = 1; i <= n;i++){
16         for(let j = 1; j <= V; j++){
17            if (j - vw[i -1][0] < 0) {
18                 dp[i][j] = dp[i -1][j]
19             } else {
20                 dp[i][j] = Math.max(
21                     dp[i -1][j],
22                     dp[i - 1][j - vw[i -1][0]] + vw[i - 1][1]
23                 )
24             }
25         }
26     }
27     return dp[n][V]
28 }
29 module.exports = {
30     knapsack : knapsack
31 };