LintCode 92. 背包问题 JavaScript算法

描述

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]

说明

你不可以将物品进行切割。

样例

- 样例 1:
	输入:  [3,4,8,5], backpack size=10
	输出:  9

- 样例 2:
	输入:  [2,3,5,7], backpack size=12
	输出:  12

挑战

O(n x m) 的时间复杂度 and O(m) 空间复杂度
如果不知道如何优化空间O(n x m) 的空间复杂度也可以通过.

解析

背包问题也是前端算法的经典问题之一了
f[i] 表示前 i 个物品选一些物品放入容量为 j 的背包中能否放满。

backPack = (m, A) => {
    var i, j, f = []
    for (i = 0; i < m + 1; i++) {
        f[i] = 0;
    }
    for (i = 0; i < A.length; i++) {
        for (j = m; j >= A[i]; j--) {
            f[j] = Math.max(f[j], f[j - A[i]] + A[i]);
        } 
    }
    return f[m];
}

运行结果