动态规划(Dynamic Programming,简称 DP)是一种解决最优化问题的方法。它通过将问题分解为多个子问题,存储每个子问题的解,避免重复计算,从而提高计算效率。动态规划通常适用于那些可以通过“重叠子问题”和“最优子结构”来优化的问题。
斐波那契数列的定义是:F(0) = 0
, F(1) = 1
, 且对于所有 n >= 2
,F(n) = F(n-1) + F(n-2)
。
我们可以使用动态规划来解决这个问题。动态规划的关键是避免重复计算,特别是对于相同的子问题。
function fibonacci(n) { // 定义状态数组 let dp = new Array(n + 1); // 边界条件 dp[0] = 0; dp[1] = 1; // 状态转移方程 for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } console.log(fibonacci(10)); // 输出 55
dp
来存储每一个斐波那契数值,dp[i]
表示第 i
个斐波那契数。dp[i] = dp[i - 1] + dp[i - 2]
,这是根据斐波那契数列的定义推导出来的。dp[0] = 0
和 dp[1] = 1
,这是斐波那契数列的起始值。通过动态规划方法,我们避免了重复计算,例如对于 fibonacci(10)
,我们没有重复计算 fibonacci(5)
,因为它已经在数组中存储。
背包问题(Knapsack Problem)是动态规划中一个非常经典的问题,涉及到最优化问题。在这个问题中,我们需要在给定的背包容量限制下,选择一些物品,使得它们的总价值最大。
0/1 背包问题通常是动态规划问题中非常经典的一个。其目标是在背包的容量 W
限制下,选择物品,使得物品的总价值最大。
n
个物品,每个物品都有一个重量和一个价值。W
。W
,且总价值最大。我们用 dp[i][w]
来表示前 i
个物品中,能放入容量为 w
的背包中的最大价值。
i
表示当前考虑的物品数量(从 1 到 n
)。w
表示背包的当前容量(从 0 到 W
)。对于每个物品 i
和每个容量 w
,我们有两个选择:
i
个物品放入背包,这时最大价值就是 dp[i-1][w]
,即不放这个物品时的最大价值。i
个物品放入背包,此时最大价值是 dp[i-1][w-weights[i-1]] + values[i-1]
,即在背包剩余容量 w-weights[i-1]
下,放入物品 i
后的最大价值。最终的状态转移方程是:
[ dp[i][w] = \max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1]) ]
w
的最大价值为 0:dp[0][w] = 0
。dp[i][0] = 0
。function knapsack(values, weights, W) { let n = values.length; let dp = Array(n + 1).fill().map(() => Array(W + 1).fill(0)); // 遍历每个物品 for (let i = 1; i <= n; i++) { for (let w = 1; w <= W; w++) { // 如果当前物品重量小于等于当前背包容量 if (weights[i - 1] <= w) { // 选择放或者不放当前物品,取最大值 dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]); } else { // 当前物品不能放入背包 dp[i][w] = dp[i - 1][w]; } } } return dp[n][W]; // 返回最大价值 } // 示例数据 let values = [60, 100, 120]; let weights = [10, 20, 30]; let W = 50; console.log(knapsack(values, weights, W)); // 输出 220
状态数组初始化:我们定义一个二维数组 dp[i][w]
来存储每个子问题的解。dp[i][w]
表示前 i
个物品在容量为 w
的背包中的最大价值。初始化时,所有的 dp[i][w]
都设置为 0,因为当没有物品或背包容量为 0 时,最大价值为 0。
循环遍历物品和背包容量:
i
,从第一个物品到最后一个物品。w
,从 1 到 W
。状态转移:
weights[i-1]
小于等于当前背包容量 w
,我们就有两个选择:放入物品 i
或不放。i
,最大价值就是 dp[i-1][w]
(即之前已经计算的解)。i
,最大价值是 dp[i-1][w-weights[i-1]] + values[i-1]
,即在剩余的背包容量下,添加物品 i
的价值。结果:dp[n][W]
即为我们需要的答案,表示在容量为 W
的背包中,前 n
个物品的最大价值。
考虑以下例子:
[60, 100, 120]
[10, 20, 30]
50
动态规划的最终解就是在背包容量为 50
的情况下,选择物品使得总价值最大。通过状态转移方程的计算,最终结果是 220
,即选择物品 2 和物品 3(分别有价值 100 和 120),总重量为 50
,总价值为 220
。