题意描述：
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式 第一行两个整数，N，V ，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式，输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
示例：
4 5
1 2
2 4
3 4
4 5
10
解题思路：
Alice: 这题是不是比 01 背包还有简单 ？直接按照性价比去装 ？
Bob: 没那么简单吧，都放到 01 背包后面讲解了，应该要比 01 背包难，直接按照性价比，贪心的算法去算肯定不对，包的体积是离散的，不可能装 0.5 个物品。
Alice: 也对，那还是二维动态规划 ？ dp[i][j] 表示前 i 个物品在消耗的体积 <= j 的时候的最大价值 ？
Bob: 那递推公式呢 ？dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i] * k] + k * w[i]) 然后求出不同的 k，也就是第 i 个物品到底装几个才是 dp[i][j] 最大。
Alice: 不行吧，那你求解的时候，最外层循环是 i，然后是体积 j，里面还有一个数量 k，三重循环估计要超时的。
Bob: 递推公式有问题吗 ？超时倒是可以优化，应该没问题，和 01背包一样的，就是多了一个 k，实际计算的时候很麻烦。
Alice: 01 背包的时候不是讲了状态压缩吗 ？这里能用状态压缩试试吗 ？
Bob: 可以倒是可以，不过应该还是要考虑 k 的问题，写成像这样 ？
for(let i=0; i<count; ++i){
for(let j=maxVolumn; j>=v[i]; --j){
for(let k=0; k*v[i]<=j; ++k){
dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i])
}
}
}
Alice: 这不还是三重循环吗 ？
Bob: 那要怎么改呢 ？（翻找答案，思考讲解中）
Alice: 可以这样，你看 k 的求解顺序，不就是从大到小一个一个的试吗 ？我们可以把 j 的求解顺序也改成从大到小，这样小 j 就可以把 v[i] 装进去，大 j 就能尽可能多装 v[i]，这不就实现了装多个的效果 ？
Bob: 那应该是这样 ？就这么简单 ？
for(let i=0; i<count; ++i){
for(let j=v[i]; j<=maxVolumn; ++j){
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
}
}
Alice: 提交试试 ？
Bob: 过倒是能过，我还是不太理解。我们从二维的递推关系出发，怎么就得到了一个一维的求解方式。最后的 dp 和前 i 个物品没啥关系 ？
Alice: 那就换一种思路，dp[j] 表示消耗空间 <= j 的时候的最大价值，然后我们尝试把每个物品都考虑进来，在这个过程中不断更新 dp[j]，dp[j] 在不同的循环中实际表示，前 i 个物品都考虑了，消耗空间是 j 的最大价值。
Bob: 那为啥第 i 个物品考虑的过程和第 i-1 个物品没啥关系呢 ？i-1 个物品放不放不会影响吗 ？
Alice: 有关系，我们是考虑了前 i-1 个物品之后，才考虑第 i 个物品的，这个影响是通过更新 dp[j] 来实现的。
Bob: 而考虑第 j 个物品的时候，只有放 0个，1个， 2个 … 的情况。
Alice: 也就是
for(let j=v[i]; j<=maxVolumn; ++j){
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
}
Bob： 你这么一说我有点明白了。那如果是这样，为啥 01 背包不直接从 dp[j] 开始推导呢 ？
Alice: 当然也可以这样推导，还是计算过程会不太好理解。依旧假设 dp[j] 是体积 <= j 的时候的最大价值，依次考虑每个物品并且维护 dp[j]，01 背包的关键点在于每个物品只能选一次，在考虑第 i 个物品的时候如何让他只选一次呢 ？
Bob: 把计算顺序反过来 ？像这样。那原理是什么呢 ？j 不是循环多次了吗 ？
for(let j=maxVolumn]; j>=v[i; --j){
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
}
Alice： j 循环多次，不代表放到了多个物品 i，这里的原理其实在 01 背包里面讲过了，反向循环是为了晚更新小 j，这样更新大 j 时用到的小 j 就还是老 j，那个只考虑前 i-1 个物品的老 j。
Bob: 这样就能保证每次 j - v[i] 的时候用的都是老 j 了 ？
Alice: 能，j 每次递减 -1，j - v[i] 一定小于 j。
Bob: 嚯，小小背包还能装这么多东西。
代码：
完全背包，动态规划最简思路
const fs = require('fs');
let buffer = '';
process.stdin.on('readable', () => {
const chunk = process.stdin.read();
if (chunk) {
buffer += chunk.toString()
}
});
// 输入的字符串转换为数字
const convert = (inputString) => {
const list = [];
inputString.split('\n').forEach((line) => {
const tokens = line.split(' ');
list.push(tokens.map(num => parseInt(num, 10)));
});
return list;
}
// 批量调用
const batchCall = (list, solve) => {
// 划分数据
const data = [];
let countAndVolumIndex = 0;
while(countAndVolumIndex < list.length) {
const [count, volum] = list[countAndVolumIndex];
data.push({
volum: volum,
count: count,
volumAndWeight: list.slice(countAndVolumIndex + 1, countAndVolumIndex + 1 + count)
});
countAndVolumIndex += count + 1;
}
data.forEach(item => {
if(solve && item && item.count && item.volum) {
solve(item.count, item.volum, item.volumAndWeight);
}
});
}
const solve = (count, maxVolum, volumAndWeight) => {
const dp = new Array(maxVolum + 1).fill(0);
for(let i=0; i<count; ++i){
// 第 i 个物品的体积和价值
const [ivolum, iweight] = volumAndWeight[i];
// 从第 i 个物品的体积开始到最大体积，从左到右计算，部分的 dp[j] 逐步累计多个 i 物品的最大价值
for(let j=ivolum; j<=maxVolum; ++j) {
dp[j] = Math.max(dp[j], dp[j-ivolum] + iweight);
}
}
console.log(Math.max(...dp));
}
process.stdin.on('end', function() {
batchCall(convert(buffer), solve)
});
测试用例：
20 200
24 50
42 60
20 49
7 15
48 115
4 11
3 8
7 5
52 66
50 25
5 8
9 25
14 40
9 22
55 42
40 30
35 49
33 16
12 12
65 127
571
参考：