1/0 knapsack for bank account statement

by Mykola Senyk

JavaScript

const items = [
  4540.90,
  26009.80,
  445.20,
  10279.80,
  12999.90,
  7982.73,
  2999.00,
  22199.80,
  14999.90,
  19599.90,
  8999.90,
  10599.90,
  12999.90,
  17997.00,
  11999.90,
  -445.20,
  9128.99,
  8899.80,
  3135.43,
  4073.15,
  15219.71,
  2699.80,
  32264.80,
  15599.90,
  1645.71,
  17999.90,
  15999.80,
  7019.80,
  13499.70,
  4499.00,
  11653.70,
  23199.88,
  -2612.86,
  -522.57,
  15545.60,
  5265.88,
  6499.90,
  13451.89,
  15799.90,
  26898.90,
  8968.11,
  15909.90,
  3654.70,
  3688.68,
  3559.78,
  13359.70,
  21598.80,
  9317.36,
  37769.71,
  29670.90,
  4499.90,
  10859.70,
  16499.00,
  19439.90,
  14399.90,
  6298.90,
  12408.60,
  9953.80,
  4212.71,
  12539.89,
  24048.70,
  8298.78,
  9558.88,
  14479.80,
  34085.89,
  5152.70,
  9999.90,
  6598.90,
  16967.59,
  3779.90,
  5999.90,
  5899.90,
  17317.52,
  13564.77,
  2377.80,
  6084.70,
  5598.90,
  6708.90,
  11097.60,
  7299.90,
  10889.80,
  10887.60,
  1499.90,
  5929.80,
  7999.90,
  9948.80,
  9654.80
];

class WeightCell {
	constructor(weight, index, parent) {
  	this.weight = weight;
    this.index = index;
    this.parent = parent;
  }
  
}

const n = items.length;
const goal = 149792.88;
const w = new Array(n);
w[0] = new Array(n);
for (let j = 0; j < n; j++) {
	w[0][j] = new WeightCell(0);
}

for (let i = 1; i <= n; i++) {
	w[i] = new Array(n);
  let v = items[i - 1];
  let currWeight;
	for (let j = 0; j < n; j++) {
    let prevColCell = w[i - 1, j];
    
    let cell;
		if (j == 0) {
      cell = new WeightCell(prevColCell.weight, i - 1, prevColCell);
    } else {
    	let changedCell = w[i - 1, j - 1];
      if (prevColCell.weight < changedCell.weight + v) {
        cell = new WeightCell(prevColCell.weight, i - 1, prevColCell);
        currWeight = prevColCell.weight;
      } else {
        cell = new WeightCell(changedCell.weight + v, i - 1, changedCell);
        currWeight = changedCell.weight + v;
      }
    }

    w[i, j] = cell;
  }
  console.log(`${i}...