1. 算法概述

背包问题（Knapsack Problem）是动态规划中最经典的问题类型之一，核心是在有限容量下选择物品以最大化总价值。本文重点介绍两种最常见的背包模型：

  • 01背包（0-1 Knapsack）：每件物品只能选 0 次或 1 次。
  • 完全背包（Unbounded Knapsack）：每件物品可以选任意多次（通常受容量限制）。

背包问题是许多动态规划思想的基石，也是面试和竞赛的常考题型。

2. 核心思想

01背包

  • 定义 dp[i][w]：前 i 件物品、背包容量为 w 时的最大价值。
  • 状态转移：对于第 i 件物品（重量 wt[i]，价值 val[i]）：
    • 不选：dp[i][w] = dp[i-1][w]
    • 选（容量够）：dp[i][w] = dp[i-1][w - wt[i]] + val[i]
  • 一维优化（滚动数组）：dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
  • ⭐ 关键：容量 w 必须从大到小逆序遍历，保证每件物品只选一次（避免同一物品被多次使用）。

完全背包

  • 状态定义相同，但每件物品可无限选。
  • 一维优化：dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
  • ⭐ 关键：容量 w 必须从小到大正序遍历，允许同一物品在更新后被再次使用。

一句话区分

类型 容量遍历方向 原因
01背包 逆序（W → wt[i]） 保证 dp[w-wt[i]] 来自上一轮，物品只用一次
完全背包 正序（wt[i] → W） 允许 dp[w-wt[i]] 来自本轮更新，物品可多次用

3. 算法步骤/伪代码

01背包

01_Knapsack(N, W, wt[], val[]):
    dp[0..W] = 0
    for i = 1 to N:
        for w = W down to wt[i]:
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

完全背包

Complete_Knapsack(N, W, wt[], val[]):
    dp[0..W] = 0
    for i = 1 to N:
        for w = wt[i] to W:
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

4. C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// ==================== 01背包（一维优化） ====================
int knapsack01(int W, const vector<int>& wt, const vector<int>& val) {
    int N = wt.size();
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < N; i++) {
        // 逆序遍历，保证每件物品只选一次
        for (int w = W; w >= wt[i]; w--) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

// ==================== 完全背包（一维优化） ====================
int knapsackComplete(int W, const vector<int>& wt, const vector<int>& val) {
    int N = wt.size();
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < N; i++) {
        // 正序遍历，允许同一物品被多次选取
        for (int w = wt[i]; w <= W; w++) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

// ==================== LeetCode 416: 分割等和子集 ====================
bool canPartition(const vector<int>& nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;

    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;

    for (int num : nums) {
        for (int w = target; w >= num; w--) {
            dp[w] = dp[w] || dp[w - num];
        }
    }
    return dp[target];
}

// ==================== 硬币找零（完全背包：最少硬币数） ====================
int coinChange(const vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1); // 初始化为不可能的大值
    dp[0] = 0;

    for (int coin : coins) {
        for (int w = coin; w <= amount; w++) {
            dp[w] = min(dp[w], dp[w - coin] + 1);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

// ==================== 测试 ====================
int main() {
    // ---------- 01背包测试 ----------
    // 物品重量: [2, 3, 4, 5]
    // 物品价值: [3, 4, 5, 6]
    // 背包容量: 8
    vector<int> wt01   = {2, 3, 4, 5};
    vector<int> val01  = {3, 4, 5, 6};
    int W01 = 8;
    cout << "01背包: 容量=" << W01 
         << ", 最大价值=" << knapsack01(W01, wt01, val01) << endl;
    // 期望: 10 (选物品2+4，重量3+5=8，价值4+6=10)

    // ---------- 完全背包测试 ----------
    // 物品重量: [1, 3, 4]
    // 物品价值: [15, 20, 30]
    // 背包容量: 4
    vector<int> wtComp  = {1, 3, 4};
    vector<int> valComp = {15, 20, 30};
    int WComp = 4;
    cout << "完全背包: 容量=" << WComp
         << ", 最大价值=" << knapsackComplete(WComp, wtComp, valComp) << endl;
    // 期望: 60 (选4个物品0，重量1*4=4，价值15*4=60)

    // ---------- 分割等和子集测试 ----------
    vector<int> nums = {1, 5, 11, 5};
    cout << "\n分割等和子集 [1,5,11,5]: "
         << (canPartition(nums) ? "可以" : "不可以") << endl;
    // 期望: 可以 (1+5+5 = 11)

    vector<int> nums2 = {1, 2, 3, 5};
    cout << "分割等和子集 [1,2,3,5]: "
         << (canPartition(nums2) ? "可以" : "不可以") << endl;
    // 期望: 不可以 (总和11，无法分割)

    // ---------- 硬币找零测试 ----------
    vector<int> coins = {1, 2, 5};
    int amount = 11;
    int result = coinChange(coins, amount);
    cout << "\n硬币找零: coins=[1,2,5], amount=" << amount
         << ", 最少硬币数=" << result << endl;
    // 期望: 3 (5+5+1 或 5+2+2+2，最少为3)

    amount = 3;
    coins = {2};
    result = coinChange(coins, amount);
    cout << "硬币找零: coins=[2], amount=" << amount
         << ", 最少硬币数=" << result << endl;
    // 期望: -1 (无法凑出3)

    return 0;
}

运行示例

01背包: 容量=8, 最大价值=10
完全背包: 容量=4, 最大价值=60

分割等和子集 [1,5,11,5]: 可以
分割等和子集 [1,2,3,5]: 不可以

硬币找零: coins=[1,2,5], amount=11, 最少硬币数=3
硬币找零: coins=[2], amount=3, 最少硬币数=-1

5. 复杂度分析

  • 时间复杂度：O(N × W)，其中 N 为物品数量，W 为背包容量。
    • 无论是 01 背包还是完全背包，都是两层循环。
  • 空间复杂度：O(W)（一维优化后），仅需一个长度为 W+1 的数组。
算法 时间 空间 备注
01背包 O(N×W) O(W) 逆序遍历容量
完全背包 正序遍历容量
多重背包 O(N×W×log K) 二进制拆分后转01背包

注意：当背包容量 W 很大时（如 10⁹），DP 不适用，需要考虑贪心或数学优化。

6. 应用场景

01背包应用

场景 说明
投资决策 有限资金下选择回报最高的投资组合
装箱问题 在限重下装入总价值最高的货物
分割等和子集 判断数组能否分成和相等的两半（LeetCode 416）
目标和 添加正负号使数组和为 target（LeetCode 494）
最后一块石头的重量 II 粉碎石头使剩余最小（LeetCode 1049）

完全背包应用

场景 说明
硬币找零 用最少硬币凑出指定金额（LeetCode 322）
硬币组合数 凑出指定金额的方案数（LeetCode 518）
剪绳子 整数拆分求最大乘积（LeetCode 343）
完全平方数 最少的完全平方数之和为 n（LeetCode 279）
单词拆分 字典中的单词能否拼接成目标串（LeetCode 139）

7. 经典例题

LeetCode 416. 分割等和子集

题目描述：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

解题思路：转化为 01背包问题——能否选出一些数，使得它们的和恰好为 sum/2。dp[w] 表示能否凑出容量 w。

关键代码要点：

  • 总和的奇偶性先判断，奇数直接返回 false。
  • dp[0] = true，其余初始化为 false。
  • 外层遍历每个数，内层逆序遍历容量。
  • 状态转移：dp[w] = dp[w] || dp[w - num]。

采药问题（经典 NOIP）

题目描述：有 T 个单位时间，M 株草药。每株草药有采摘时间 t[i] 和价值 v[i]。求在 T 时间内能获得的最大总价值。

解题思路：标准 01背包——容量为 T，物品重量为 t[i]，价值为 v[i]。

硬币找零（LeetCode 322）

题目描述：给定不同面额的硬币和一个总金额。计算可以凑成总金额所需的最少硬币个数。如果无法凑出，返回 -1。

解题思路：完全背包——每种硬币可以无限使用。dp[w] 表示凑出金额 w 所需的最少硬币数。初始化为 amount+1（不可能的大值），dp[0] = 0。正序遍历容量，每次取 min。

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 29ms
  4. Powered by Hydro v5.0.1 Community