动态规划-背包问题

什么是**背包问题 (Knapsack Problem)**？

背包问题是动态规划里非常经典的一类问题。
最常见的版本是 0/1 背包：

有一个背包，容量为 W（整数）。

有 N 个物品，每个物品有：

• 重量 w[i]
• 价值 v[i]

每个物品只能选 0 次或 1 次（不能切开，也不能重复选）。

目标：让背包里装的东西总重量 ≤ W，同时总价值最大。

背包问题解法

利用动态规划（DP）解法

• 用一个二维数组：

  dp[i][j] = 前 i 个物品中，总重量不超过 j 时，最大价值

• 初始化：当 i=0（不考虑任何物品时）：

  dp[0][j] = 0  // 什么都不装，价值是 0

• 状态转移方程
  • 不选：

    dp[i][j] = dp[i-1][j]

  • 选（前提：j >= w[i-1]）：

    dp[i][j] = dp[i-1][j - w[i-1]] + v[i-1]

  • 取最大值

    dp[i][j] = max(
      dp[i-1][j],  
      dp[i-1][j - w[i-1]] + v[i-1]
    )

• 结果

  dp[N][W]

例题

题目链接：https://leetcode.cn/problems/perfect-squares/solutions/823192/dai-ma-sui-xiang-lu-279-wan-quan-ping-fa-9ieo/?envType=study-plan-v2&envId=dynamic-programming

完全平方数问题

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

分析

动态规划一般按以下顺序来进行。

1. 确定dp数组
   dp[j]：和为j的完全平方数的最少数量为dp[j]
2. 确定递推公式
   递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);
3. dp数组初始化
   非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。
4. 确定遍历顺序
   我们知道这是完全背包，如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。

// 先遍历物品，再遍历背包
var numSquares1 = function(n) {
    let dp = new Array(n + 1).fill(Infinity)
    dp[0] = 0

    for(let i = 1; i**2 <= n; i++) {
        let val = i**2
        for(let j = val; j <= n; j++) {
            dp[j] = Math.min(dp[j], dp[j - val] + 1)
        }
    }
    return dp[n]
};
// 先遍历背包，再遍历物品
var numSquares2 = function(n) {
    let dp = new Array(n + 1).fill(Infinity)
    dp[0] = 0

    for(let i = 1; i <= n; i++) {
        for(let j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i - j * j] + 1, dp[i])
        }
    }

    return dp[n]
};