看了背包问题的解答没有js的, 就写了这个

题目描述

有 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

输出样例：

8

JS解法

var fs = require('fs');
var buf = '';

process.stdin.on('readable', function() {
  var chunk = process.stdin.read();
  if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() { // 统一处理输入信息
  var lines = buf.split('\n')
  var line = lines.shift()
  line = line.split(' ')
  var n = parseInt(line[0])
  var m = parseInt(line[1])
  var v = []
  var w = []
  for(var i = 0; i < lines.length; i++) {
    line = lines[i].split(' ')
    v.push(parseInt(line[0]))
    w.push(parseInt(line[1]))
  }
  var f = [[]]
  // 初始化第一行
  for(var j = 0; j < m + 1; j++) {
    if(j < v[0]) {
      f[0][j] = 0
    } else {
      f[0][j] = w[0]
    }
  }

  for(i = 1; i < n; i++){
    f[i] = []; // 初始化一行
    for (j = 0; j < m + 1; j++) {
      f[i][j] = f[i - 1][j];
      if(j >= v[i]) {
        f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]); 
        // 状态转移, 应为只有一个第i号物品, 
        // 故放进去的时候考虑的是f[i - 1][j - v[i]]
      }
    }
  }
  console.log(f[n - 1][m])
});