js:数据结构笔记14--高级算法

动态规划：

递归是从顶部开始将问题分解，通过解决所有分解出小问题来解决整体问题；

动态规划从底部开始解决问题，将所有小问题解决，然后合并掉一个整体解决方案；

　　

function dynFib(n) {
	var val = [];
	for(var i = 1; i <= n; ++i) {
		val[i] = 1;
	}
	if(n === 1) {
		return 1;
	} else {
		for(var i = 2; i <= n; ++i) {
			val[i] = i * val[i-1];
		}
		return val[n];
	}
}

function iterFib(n) {
	var last = 1,
	    result = 1;
	for(var i = 2; i <= n; ++i) {
		result = last * i;
		last = result;
	}
	return result;
}

背包问题：

• 递归解决：

function max(a,b) {
	return (a > b) ?  a : b;
}
function knapsack(capacity,size,value,n) {
	if(n == 0 || capacity ==0) {
		return 0;
	}
	if(size[n -1] > capacity) {
		return knapsack(capacity,size,value,n-1);
	} else {
		return max(value[n - 1] + 
					knapsack(capacity - size[n - 1],size,value,n-1),
					knapsack(capacity,size,value,n-1));
	}
}

var value = [4,5,10,11,13],
	size = [3,4,7,8,9],
	capacity = 16,
	n = 5;
console.log(knapsack(capacity,size,value,n));

• 　动态规划：

function max(a,b) {
	return (a > b) ?  a : b;
}
function dknapsack(capacity,size,value,n) {
	var k = [];
	for(var i = 0; i <= capacity + 1; ++i) {
		k[i] = [];
	}
	for(var i = 0; i <= n; ++i) {
		for(var w = 0; w <= capacity; ++w) {
			if(i == 0 || w == 0) {
				k[i][w] = 0;
			} else if(size[i - 1] <= w) {
				k[i][w] = max(value[i - 1] + k[i - 1][w - size[i - 1]], k[i - 1][w]);
			} else {
				k[i][w] = k[i - 1][w];
			}
		}
	}
	return k[n][capacity];
}

var value = [4,5,10,11,13],
	size = [3,4,7,8,9],
	capacity = 16,
	n = 5;
console.log(dknapsack(capacity,size,value,n));