20
2019
03

0-1背包问题

背包问题(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));

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



« 上一篇下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。