Rod-Cutting
opt[0] = 0 sol[0] = [] for k = 1 to price.length opt[k] = 0 sol[k] = null for i = 1 to k if opt[k] < opt[k-i] + price[i] opt[k] = opt[k-i] + price[i] sol[k] = sol[k-i] + [i]