【数据结构与算法】三个经典案例带你了解动态规划

[
	[true, true, false, true],
	[false, false, true, true],
	[true, false, false, false],
	[false, false, false, true]
]

function fibonacci1(n) {
	if(n == 1 || n == 2) return 1;
	return fibonacci(n - 1) + fibonacci(n - 2)
}

function fibonacci2(n) {
	// 记录斐波那契数列 第1个数 到 第n个数 的所有值
	let arr = [1, 1]
	// 获取n个数之前所有的值，并存储在arr中
	for(let i = 2; i < n; i++) {
		arr[i] = arr[i - 1] + arr[i - 2]
	}
	
	// 直接从arr中返回我们要的值
	return arr[n - 1]
}

// 递归求取的开始时间
let start1 = Date.now()
// 递归求取第40个数的值
console.log(fibonacci1(40))
// 递归求取的结束时间
let end1 = Date.now()

// 动态规划求值的开始时间
let start2 = Date.now()
// 动态规划求取第40个数的值
console.log(fibonacci2(40));
// 动态规划求值的结束时间
let end2 = Date.now()

console.log(`
递归所用时间：${end1 - start1} ms
动态规划所用时间：${end2 - start2} ms
`);
/*
102334155
102334155

递归所用时间：2476 ms
动态规划所用时间：0 ms
*/

function publicStr(s1, s2) {
    // 创建一个表
    let table = []

    // 记录最大的公共子串长度
    let max = 0

    // 子串进行比较，将表填完整
    for(let i = 0; i <= s1.length; i++) {
        table[i] = []
        for(let j = 0; j <= s2.length; j++) {
        	// 若行表头或列表头为0，格子里填0
            if(i == 0 || j == 0) table[i][j] = 0;
            // 若字符比对不相同
            else if(s1[i - 1] !== s2[j - 1]) table[i][j] = 0;
            // 字符比对相同
            else {
            	// 当前格子的值等于左上角格子的值+1
                table[i][j] = table[i - 1][j - 1] + 1
                // 判断max是否为最大公共子串的长度
                if(table[i][j] > max) max = table[i][j]
            } 
        }
    }

    // 记录所有的最大公共子串的信息
    let items = []
    
    // 遍历整个表，找到所有子串长度为max的子串的最后一个字符的索引
    for(let i = 0; i < s1.length; i ++) {
        let current = table[i]

        for(let j = 0; j < s2.length; j ++) {
            if(current[j] === max) items.push(i)
        }
    }

    console.log(`最大子串长度为${max}`);
    console.log(`长度为${max}的子串有：`);
    for(let i in items) {
        let start = items[i] - max
        console.log(`${s1.slice(start, start + max)}`);
    }
}

let s1 = 'abaccd'
let s2 = 'badacef'

publicStr(s1, s2)
/* 打印结果：
	最大公共子串长度为2
	长度为2的子串有：
	ba
	ac
	表：[
		  [0, 0, 0, 0, 0, 0, 0, 0],
		  [0, 0, 1, 0, 1, 0, 0, 0],
		  [0, 1, 0, 0, 0, 0, 0, 0],
		  [0, 0, 2, 0, 1, 0, 0, 0],
		  [0, 0, 0, 0, 0, 2, 0, 0],
		  [0, 0, 0, 0, 0, 1, 0, 0],
		  [0, 0, 0, 1, 0, 0, 0, 0]
		]
*/

// 封装一个判断大小的函数
function max(v1, v2) {
	return v1 > v2 ? v1 : v2
}

// 主函数，用于判断当前背包容量下，存放某个物品的最大收益
// 参数：背包容量、存放每个物品重量的数组、存放每个物品价值的数组、物品标号
function knapsack(capacity, size, value, n) {
	// 如果没有物品了或者背包没容量了，则最大收益为0
	if(n == 0 || capacity == 0) return 0;
	// 物品n的重量大于背包容量
	else if(size[n - 1] > capacity) {
		// 返回上一个物品的最大收益
		return knapsack(capacity, size, value, n - 1)
	}
	// 物品n的重量小于背包容量
	else {
		// 此时有两种选择：第一种：拿该物品 ; 第二种：不拿该物品
		// 我们要取其中收益最大的方案，因此用到max函数
		return max(value[n - 1] + knapsack(capacity - size[n - 1], size, value, n - 1), knapsack(capacity, size, value, n - 1))
	}
}

// 代码测试
let capacity = 8
let size = [3, 3, 4, 5]
let value = [4, 6, 7, 9]
let n = 4
let res = knapsack(capacity, size, value, n)
console.log(res)        // 15 , 表示最大收益价值为15

function knapsack(capacity, size, value, n) {
    // 返回较大的值
    function max(v1, v2) {
        return v1 > v2 ? v1 : v2
    }

    let table = []

    // 生成长度为n的表
    for(let i = 0; i <= n; i++) {
        table[i] = []
    }
    
    // 判断每种物品面对不同背包容量时的最大收益
    for(let i = 0; i <= n; i++) {
        for(let j = 0; j <= capacity; j++) {
            // 物品种类序列为0或者背包容量为0时，最大收益为0
            if(i == 0 || j == 0) table[i][j] = 0;
            // 背包容量小于物品重量时，最大收益等于上一种物品在此背包容量下的最大收益
            else if(size[i - 1] > j) {
                table[i][j] = table[i - 1][j]
            }
            /* 背包容量大于物品重量时，最大收益分两种情况：
               第一种情况：不放此物品。则最大收益等于上一种物品在此背包容量下的最大收益；
               第二种情况：放此物品。则最大收益等于该物品的收益加上剩余背包容量下，上一种物品的最大收益
            */ 
            else {
                table[i][j] = max(table[i - 1][j], value[i - 1] + table[i - 1][j - size[i - 1]])
            }
        }
    }

    // 最大收益值
    let max_value = 0
    let which = -1
    // 寻找在背包容量为capacity时的最大收益值，以及最大收益值所对应的物品种类
    for(let i in table) {
        let k = table[i][capacity]
        if(k > max_value) {
            max_value = k
            which = i
        } 
    }

    // 记录所装的物品
    let goods = []
    // 记录背包剩余容量
    let rest = capacity
    
    while(rest > 0 && which > 0) {
        // 若此时的最大收益不等于上一种物品在此背包容量下的最大收益，则放了此物品；否则就没放此物品
        if(table[which][rest] !== table[which - 1][rest]) {
            goods.push(which)
            rest -= size[which - 1]         
        }
        which --
    }

    console.log(`背包最大的收益为：${max_value}，拿取的物品有${goods.join(',')}`);
}

let size = [3, 3, 4, 5]
let value = [4, 6, 7, 9]
let capacity = 8
let n = 4

knapsack(capacity, size, value, n)
/*	打印结果：
	背包最大的收益为：15，拿取的物品有4,2
	表：[
		  [0, 0, 0, 0, 0, 0, 0, 0, 0],
		  [0, 0, 0, 4, 4, 4, 4, 4, 4],
		  [0,  0,  0,  6, 6, 6, 10, 10, 10],
		  [0,  0,  0,  6, 7, 7, 10, 13, 13],
		  [0,  0,  0,  6, 7, 9, 10, 13, 15]
		]
*/