01背包（二维数组）
i 来表示物品、j表示背包容量。
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
先遍历物品还是背包都可以
const readline = require('readline').createInterface({input: process.stdin,output: process.stdout
});let input = [];readline.on('line', (line) => {input.push(line);
});readline.on('close', () => {let [n, bagweight] = input[0].split(' ').map(Number);let weight = input[1].split(' ').map(Number);let value = input[2].split(' ').map(Number);let dp = Array.from({length:n},()=>Array(bagweight+1).fill(0))for(let i = 0;i<n;i++){dp[i][0] = 0}for(let j=0;j<=bagweight;j++){if(weight[0]<=j){dp[0][j] = value[0]}}for(let i=1;i<n;i++){for(let j=1;j<=bagweight;j++){if(j-weight[i]>=0){dp[i][j] = Math.max(dp[i-1][j],value[i]+dp[i-1][j-weight[i]])}else{dp[i][j] = dp[i-1][j]}}}console.log(dp[n-1][bagweight])
})
01背包（一维数组）
dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
一维dp遍历的时候，背包是从大到小.倒序遍历是为了保证物品i只被放入一次.且for循环的顺序不能颠倒。
对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖.所以不用倒序
const readline = require('readline').createInterface({input: process.stdin,output: process.stdout
});let input = [];readline.on('line', (line) => {input.push(line);
});readline.on('close', () => {let [n, bagweight] = input[0].split(' ').map(Number);let weight = input[1].split(' ').map(Number);let value = input[2].split(' ').map(Number);let dp = Array.from({length:bagweight+1}).fill(0)for(let i = weight[0];i<=bagweight;i++){dp[i] = value[0]}for(let i=1;i<n;i++){for(let j=bagweight;j>=weight[i];j--){dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i])}}console.log(dp[bagweight])
})
完全背包
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
完全背包的物品是可以添加多次的，所以要从小到大去遍历
在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！
const readline = require('readline').createInterface({input: process.stdin,output: process.stdout
});let input = [];readline.on('line', (line) => {input.push(line);
});readline.on('close', () => {let [n, bagweight] = input[0].split(' ').map(Number);let weight = []let price = []for(let i=1;i<=n;i++){let item = input[i].split(' ').map(Number)weight.push(item[0])price.push(item[1])}let dp = Array.from({length:bagweight+1}).fill(0)for(let i=0;i<n;i++){for(let j = weight[i];j<=bagweight;j++){dp[j] = Math.max(dp[j],price[i]+dp[j-weight[i]])}}console.log(dp[bagweight])
})