Finding the most profitable way to cut a rod, using bottom-up dynamic programming (CLRS Section 15.1)

rod_cutting.js

var assert = require("assert");

class Result {
	constructor(n, seq, score) {
		this.n = n;
		this.seq = seq;
		this.score = score;
	}

	betterThan(other) {
		assert(this.n == other.n, "Unable to compare rods of different lengths");
		return this.score > other.score;
	}
}

function findOptimalSplit(n, costs) {
	console.log("Finding optimal split for " + n + ":");
	var cache = {};
	cache[0] = new Result(0, [], 0);
	for (var i = 1; i <= n; i++) {
		console.log(" - subproblem " + i);
		var best = null;
		for (var j = 1; j <= i; j++) {
			assert(costs[j] >= 0, "No cost defined for length " + j);
			var left = new Result(j, [j], costs[j]);
			var right = cache[i - j];
			var combined = new Result(left.n + right.n,
					left.seq.concat(right.seq),
					left.score + right.score);

			console.log("   - " + combined.score + " for " + combined.seq.join(" + "));
			if (!best || combined.betterThan(best)) {
				best = combined;
			}
		}

		assert(best);
		cache[i] = best;
	}

	return cache[n].seq;
}

console.log(findOptimalSplit(10, [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]));