当前位置：首页 > news >正文

一篇吃透所有常见背包问题（含例题+代码+详细解析）

news 2026/4/24 11:20:26

背包问题是算法面试中最经典、最常考的动态规划题型之一，核心围绕「物品选择」与「容量限制」展开，衍生出多种变体，但本质逻辑高度统一。本文将全面梳理所有常见背包类型，从基础的一维01背包、完全背包，到进阶的多重背包、二维背包，再到特殊的分组背包，每类均搭配核心思路+例题解析+可直接运行代码，兼顾入门理解与实战应用，看完就能搞定各类背包面试题。

本文适合：算法入门者、准备面试的应届生、需要巩固动态规划基础的开发者，所有代码均为C++实现（最贴合面试场景），注释详细，可直接复制提交LeetCode。

一、背包问题核心共性

所有背包问题的本质的是：在给定「物品属性」和「背包容量限制」的前提下，选择若干物品，达到某种最优目标（最大价值、最多数量、最少花费等）。

核心要素拆解：

物品：有自身属性（如重量、价值、数量限制等）；
背包：有容量限制（可是1个维度，也可是多个维度）；
选择规则：物品可选1次（01）、无限选（完全）、有限次（多重）、分组选（分组）；
动态规划核心：用dp数组记录「不同容量下的最优解」，通过状态转移方程递推，避免重复计算。

所有背包问题的解题步骤高度统一：

定义dp数组含义（核心，决定后续转移方程）；
确定初始化条件（dp[0]或dp[0][0]等基础状态）；
确定遍历顺序（物品、容量的先后顺序，正序/倒序，直接决定解题正确性）；
推导状态转移方程（核心逻辑，不同背包仅此处有差异）；
返回最终目标值（通常是dp[最大容量]或dp[最大容量1][最大容量2]）。

二、常见背包类型详解（按难度递增）

2.1 01背包（物品只能选1次）

2.1.1 核心定义

最基础的背包类型：有n个物品，每个物品只能选择1次，每个物品有「重量weight[i]」和「价值value[i]」，背包有最大容量W，求能装入背包的最大价值。

2.1.2 核心思路

dp数组定义：dp\[j\]表示「背包容量为j时，能装入的最大价值」；
初始化：dp\[0\] = 0（容量为0时，价值为0），其余dp[j]初始化为0（或负无穷，根据题意调整）；
遍历顺序：先遍历物品，后遍历容量，且容量必须倒序遍历；
- 倒序原因：避免同一物品被多次选择（01背包只能选1次），倒序能保证每个物品仅被计算1次；
- 若正序遍历，会导致物品被重复选取（变成完全背包）。
状态转移方程：对于每个物品i，遍历容量j从W到weight[i]：
dp\[j\] = max\(dp\[j\], dp\[j \- weight\[i\]\] \+ value\[i\]\)解释：容量为j时，有两种选择——不选物品i（dp[j]不变），或选物品i（价值为dp[j - weight[i]] + value[i]），取两者最大值。

2.1.3 例题：LeetCode 416. 分割等和子集

题目描述

给你一个只包含正整数的非空数组nums，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例：输入nums = [1,5,11,5] → 输出true（[1,5,5]和[11]的和均为11）。

解题分析

本题本质是「01背包的变形」：

背包容量：数组总和的一半（若总和为奇数，直接返回false）；
物品：数组中的每个元素（重量=元素值，价值=元素值）；
目标：判断是否能选出若干物品，使其重量和等于背包容量（即价值和等于容量）。

代码实现（带详细注释）

classSolution{public:boolcanPartition(vector<int>&nums){intsum=0;for(intnum:nums)sum+=num;// 总和为奇数，无法分割成两个相等的子集if(sum%2!=0)returnfalse;inttarget=sum/2;// 背包容量// dp[j]：容量为j时，能装入的最大价值（此处价值=重量）vector<int>dp(target+1,0);// 01背包：先遍历物品，后倒序遍历容量for(intnum:nums){// 遍历每个物品（num是物品重量和价值）// 倒序遍历容量，避免物品重复选取for(intj=target;j>=num;j--){// 状态转移：选或不选当前物品dp[j]=max(dp[j],dp[j-num]+num);}}// 若最大价值等于目标容量，说明能分割returndp[target]==target;}};

2.1.4 关键注意点

01背包的核心是「倒序遍历容量」，只要记住：物品只能选1次 → 倒序，后续所有01背包变体（如二维01背包）都遵循这个规则。

2.2 完全背包（物品可无限选）

2.2.1 核心定义

与01背包唯一区别：每个物品可以无限次选择（只要背包容量足够），其余条件（物品重量、价值，背包容量）不变。

2.2.2 核心思路

dp数组定义：与01背包一致，dp\[j\]表示「背包容量为j时，能装入的最大价值」；
初始化：与01背包一致；
遍历顺序：先遍历物品，后遍历容量，且容量正序遍历；
- 正序原因：允许同一物品被多次选择（正序遍历会让物品重复参与计算，实现「无限选」）。
状态转移方程：与01背包一致（仅遍历顺序不同）：dp\[j\] = max\(dp\[j\], dp\[j \- weight\[i\]\] \+ value\[i\]\)

补充：完全背包还有「先遍历容量，后遍历物品」的写法，用于解决「排列问题」（下文会详细说明）。

2.2.3 例题1：LeetCode 322. 零钱兑换（求最少硬币数）

题目描述

给你一个整数数组coins，表示不同面额的硬币；另给一个整数amount，表示总金额。请你计算并返回可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。

示例：输入coins = [1,2,5], amount = 11 → 输出3（5+5+1）。

解题分析

本题是「完全背包的最小值问题」：

背包容量：amount（总金额）；
物品：硬币（重量=面额，价值=1，因为要统计硬币个数）；
目标：凑成容量amount，所需的最少价值（硬币个数）。

注意：最小值问题的初始化的是「无穷大」，只有dp[0] = 0（0金额需要0个硬币）。

代码实现（带详细注释）

classSolution{public:intcoinChange(vector<int>&coins,intamount){// dp[j]：凑成金额j所需的最少硬币个数// 初始化：无穷大（表示无法凑成），dp[0] = 0vector<int>dp(amount+1,INT_MAX);dp[0]=0;// 完全背包：先遍历物品（硬币），后正序遍历容量（金额）for(intcoin:coins){// 正序遍历，允许硬币重复使用for(intj=coin;j<=amount;j++){// 只有dp[j - coin]不是无穷大，才可以更新dp[j]if(dp[j-coin]!=INT_MAX){dp[j]=min(dp[j],dp[j-coin]+1);}}}// 若dp[amount]还是无穷大，说明无法凑成，返回-1returndp[amount]==INT_MAX?-1:dp[amount];}};

2.2.4 例题2：LeetCode 518. 零钱兑换 II（求组合数）

题目描述

给你一个整数数组coins表示不同面额的硬币，另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例：输入coins = [1,2,5], amount = 5 → 输出4（[1,1,1,1,1]、[1,1,3]、[1,4]、[5]）。

解题分析

本题是「完全背包的组合数问题」，核心是「不考虑顺序」（[1,2]和[2,1]算同一种组合）：

遍历顺序：先遍历物品（硬币），后遍历容量（金额），保证组合的无序性（先固定硬币顺序，避免重复计数）；
dp数组定义：dp\[j\]表示「凑成金额j的组合数」；
初始化：dp\[0\] = 1（凑成0金额，只有1种方法：不选任何硬币）。

代码实现（带详细注释）

classSolution{public:intchange(intamount,vector<int>&coins){// dp[j]：凑成金额j的组合数vector<unsignedint>dp(amount+1,0);dp[0]=1;// 初始化：0金额有1种凑法// 完全背包-组合：先遍历物品（硬币），后正序遍历容量（金额）for(intcoin:coins){for(intj=coin;j<=amount;j++){// 状态转移：凑成j的组合数 = 不选当前硬币的组合数 + 选当前硬币的组合数（dp[j - coin]）dp[j]+=dp[j-coin];}}returndp[amount];}};

注意：由于组合数可能很大，用unsigned int避免int溢出（极端用例可改用unsigned long long）。

2.2.5 例题3：LeetCode 377. 组合总和 Ⅳ（求排列数）

题目描述

给你一个由不同整数组成的数组nums，和一个目标整数target，请你从nums中找出并返回总和为target的元素组合的个数。顺序不同的序列被视作不同的组合。

示例：输入nums = [1,2,3], target = 4 → 输出7（[1,1,1,1]、[1,1,2]、[1,2,1]、[2,1,1]、[1,3]、[3,1]、[2,2]）。

解题分析

本题是「完全背包的排列数问题」，核心是「考虑顺序」（[1,2]和[2,1]算两种排列）：

遍历顺序：先遍历容量（target），后遍历物品（nums），允许不同顺序的组合被计数（每个容量下，所有物品都能重新选择，实现顺序多样性）；
dp数组定义：与组合数一致，dp\[j\]表示「凑成总和j的排列数」；
初始化：dp\[0\] = 1（同上）。

代码实现（带详细注释）

classSolution{public:intcombinationSum4(vector<int>&nums,inttarget){// dp[j]：凑成总和j的排列数vector<unsignedint>dp(target+1,0);dp[0]=1;// 初始化：0总和有1种凑法// 完全背包-排列：先遍历容量（target），后遍历物品（nums）for(intj=1;j<=target;j++){for(intnum:nums){// 只有j >= num，才能选当前物品if(j>=num){dp[j]+=dp[j-num];}}}returndp[target];}};

2.2.6 完全背包关键总结

核心：物品可无限选 → 正序遍历容量；
组合数（无序）：先物品 → 后背包；
排列数（有序）：先背包 → 后物品；
最小值/最大值问题：遍历顺序与组合数一致（先物品，后背包）。

2.3 二维背包（多容量限制）

2.3.1 核心定义

在一维背包的基础上，增加一个容量限制（即两个容量维度），物品仍遵循「01背包」或「完全背包」的选择规则。最常见的是「01二维背包」。

例：物品有两个属性（如重量、体积），背包有两个容量限制（最大重量、最大体积），求能装入的最大价值。

2.3.2 核心思路

dp数组定义：dp\[i\]\[j\]表示「背包容量1为i、容量2为j时，能装入的最大价值」；
初始化：dp\[0\]\[0\] = 0，其余根据题意初始化（最大值问题初始化为0，最小值问题初始化为无穷大）；
遍历顺序：
- 01二维背包：先遍历物品，后倒序遍历两个容量；
- 完全二维背包：先遍历物品，后正序遍历两个容量。
状态转移方程（以01二维背包为例）：
设物品的两个属性为a[i]、b[i]，价值为v[i]，则：dp\[i\]\[j\] = max\(dp\[i\]\[j\], dp\[i \- a\[i\]\]\[j \- b\[i\]\] \+ v\[i\]\)条件：i >= a[i] 且 j >= b[i]（两个容量均满足）。

2.3.3 例题：LeetCode 474. 一和零

题目描述

给你一个二进制字符串数组strs和两个整数m和n。请你找出并返回strs的最大子集的大小，该子集中最多有m个0和n个1。

示例：输入strs = ["10","0001","111001","1","0"], m = 5, n = 3 → 输出4（选["10","0001","1","0"]，共3个0和2个1）。

解题分析

本题是「01二维背包的最大值问题」：

两个容量限制：m（最多0的个数）、n（最多1的个数）；
物品：每个字符串（属性1：含0的个数，属性2：含1的个数，价值：1，因为要统计子集大小）；
目标：两个容量均不超过限制时，能选择的最大物品个数（价值和）。

代码实现（带详细注释）

classSolution{public:intfindMaxForm(vector<string>&strs,intm,intn){// dp[i][j]：最多i个0、j个1时，能选择的最大字符串个数vector<vector<int>>dp(m+1,vector<int>(n+1,0));// 01二维背包：先遍历物品（每个字符串），后倒序遍历两个容量for(auto&str:strs){// 加&避免复制，提升效率intzero=0,one=0;// 统计当前字符串的0和1的个数（物品的两个属性）for(charc:str){c=='0'?zero++:one++;}// 倒序遍历两个容量，避免物品重复选择for(inti=m;i>=zero;i--){for(intj=n;j>=one;j--){// 状态转移：选或不选当前字符串dp[i][j]=max(dp[i][j],dp[i-zero][j-one]+1);}}}returndp[m][n];}};