hanyeah

背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

如下，求出了最高价格，可以在此基础上求出物品放置方案。

var values = [2,4,1,5,3];
var weights = [4,5,6,3,2];
var maxWeight = 12;
function calc(i, w) {
	if(i>=weights.length || w <= 0) {
		return 0;
	}
	if(weights[i] <= w) {
		return Math.max(
			calc(i + 1, w - weights[i]) + values[i],
			calc(i + 1, w)
			);
	} else {
		return calc(i + 1, w);
	}
}

console.log(calc(0, maxWeight));

以上算法应该属于分治算法，可以改成动态规划。为了看清楚原理，还是保留最原始的算法。