采购方案（背包计数）

题目描述

爱丽丝正在为制作新的人偶准备素材。她需要购买 n 种不同的素材，每种素材的单价分别为 a₁, a₂, …, aₙ。为了保证每一种人偶都能顺利完成，她必须为每种素材至少购买一个。

现在爱丽丝手中恰好有 b 元，她希望知道有多少种不同的采购方案，能够恰好耗尽这 b 元预算。需要注意的是，即使两种素材的单价相同，它们也被视为不同的素材种类。

数据范围：

• 0 ≤ b ≤ 100
• 1 ≤ n ≤ 10
• 1 ≤ aᵢ ≤ 50

示例

输入：

10
1 2

输出： 4

说明：

• 每种素材至少买一个，消耗 1 + 2 = 3 元，剩余 7 元
• 使用单价 1 和 2 凑 7 元的方案：
  1. 7 个单价 1
  2. 5 个单价 1 + 1 个单价 2
  3. 3 个单价 1 + 2 个单价 2
  4. 1 个单价 1 + 3 个单价 2
• 共 4 种方案

解题思路

核心：完全背包求方案数

1. 预扣最小成本：每种素材至少买一个，总最小成本 = Σ aᵢ。剩余预算 = b - Σ aᵢ。若剩余 < 0，直接返回 0。

2. 完全背包计数：dp[j] 表示剩余预算中凑出金额 j 的方案数。

   • 初始化：dp[0] = 1
   • 转移：对于每种素材 coin，正序遍历 j：dp[j] += dp[j - coin]
   • 正序遍历保证每种素材可以无限次使用（完全背包特性）

3. 为什么外层循环遍历素材？ 因为素材是不同的种类。外层循环决定物品放入顺序，考虑的是“前 i 种素材”的子问题。

解法对比

代码实现

/**
 * 一维完全背包（推荐）
 * 每种素材至少买一个 → 预扣成本 + 完全背包
 */
function getNumOfBuy(coins, amount) {
    const leastCost = coins.reduce((a, b) => a + b, 0);
    const remain = amount - leastCost;
    if (remain < 0) return 0;

    const dp = new Array(remain + 1).fill(0);
    dp[0] = 1;

    for (const coin of coins) {
        for (let j = coin; j <= remain; j++) {
            dp[j] += dp[j - coin];
        }
    }

    return dp[remain];
}

/**
 * 二维完全背包（更好理解）
 */
function getNumOfBuy2D(coins, amount) {
    const leastCost = coins.reduce((a, b) => a + b, 0);
    const remain = amount - leastCost;
    if (remain < 0) return 0;

    const n = coins.length;
    const dp = Array.from({ length: n + 1 }, () => new Array(remain + 1).fill(0));
    dp[0][0] = 1;

    for (let i = 1; i <= n; i++) {
        const coin = coins[i - 1];
        for (let j = 0; j <= remain; j++) {
            for (let k = 0; k * coin <= j; k++) {
                dp[i][j] += dp[i - 1][j - k * coin];
            }
        }
    }

    return dp[n][remain];
}

/**
 * 01背包版本（每种素材最多买一个, 仅作对比）
 */
function getNumOfBuy01(coins, amount) {
    const leastCost = coins.reduce((a, b) => a + b, 0);
    const remain = amount - leastCost;
    if (remain < 0) return 0;

    const dp = new Array(remain + 1).fill(0);
    dp[0] = 1;

    for (const coin of coins) {
        for (let j = remain; j >= coin; j--) {  // 倒序是关键区别
            dp[j] += dp[j - coin];
        }
    }

    return dp[remain];
}

复杂度分析

• 时间复杂度： O(n × remainBudget)，n ≤ 10，remainBudget ≤ 100，非常快。
• 空间复杂度： O(b)，一维 dp 数组。

10
1 2

4