彻底吃透背包问题：01背包、完全背包、分组背包（精简版）

前言：背包问题是DP经典考点，新手常被循环顺序、状态转移搞晕。本文精简核心内容，聚焦3类核心背包的原理、代码和易错点，看完直接上手刷题。核心约定：背包最大容量V，物品总数n（分组背包为组数G）物品：体积w[i]、价值v[i]；dp[j]：容量j时的最大价值核心目标：不超容量前提下，获得最大价值PS：所有C++代码精简可直接提交，适配竞赛、LeetCode刷题场景。一、背包问题本质有限资源的最优分配，遵循DP四步走：定义状态→转移方程→初始化→遍历顺序，核心是复用子问题答案，避免重复计算。二、01背包（每个物品仅选1次）核心要点状态转移方程：$$dp[j] = \max(dp[j], dp[j - w[i]] + v[i])$$关键：内层逆序枚举容量（j从V到w[i]），防止物品重复选择。标准C++代码#include iostream #include algorithm #include cstring using namespace std; const int MAXN = 1005; int w[MAXN], v[MAXN], dp[MAXN]; int main() { int n, V; cin n V; memset(dp, 0, sizeof(dp)); for (int i = 1; i = n; i++) cin w[i] v[i]; // 核心：外层物品，内层逆序容量 for (int i = 1; i = n; i++) for (int j = V; j = w[i]; j--) dp[j] = max(dp