核心概念讲解
**动态规划（DP）**的核心思想是 “把大问题拆成小问题，用小问题的答案拼出大问题的解”。它有两个关键性质：
最优子结构：大问题最优解包含小问题最优解（比如背包最大价值由子背包决定）
无后效性：当前状态只与历史有关，与未来无关
以背包为例，定义 dp[j] 表示背包容量为 j 时的最大价值。转移方程如下：
$$
dp[j] = \max(dp[j], dp[j - w[i]] + v[i])
$$
其中 w[i] 是第 i 件物品的重量，v[i] 是它的价值。
完全背包 vs 01背包
完全背包
特点：每种物品可无限取
关键区别：内层循环采用 正序遍历，确保每个物品可以被多次选取
for (int j = w[i]; j <= W; ++j) { // 正序
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
01背包
特点：每种物品最多选一次
关键区别：内层循环采用 逆序遍历，防止同一物品被重复计数
for (int j = W; j >= w[i]; --j) { // 逆序
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
C++代码示例
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005; // 最大物品数量
const int MAXW = 2000005; // 背包容量上限（根据实际题目调整）
struct Item {
int weight;
int value;
} items[MAXN];
// dp数组初始化：所有元素初始化为0（默认空背包价值为0）
int dp[MAXW];
void knapsack_complete(int n, int W) {
for (int i = 1; i <= n; ++i) { // 遍历物品
for (int j = items[i].weight; j <= W; ++j) { // 正序遍历背包容量
if (dp[j - items[i].weight] + items[i].value > dp[j]) {
dp[j] = dp[j - items[i].weight] + items[i].value;
}
}
}
}
void knapsack_01(int n, int W) {
for (int i = 1; i <= n; ++i) { // 遍历物品
for (int j = W; j >= items[i].weight; --j) { // 逆序遍历背包容量
if (dp[j - items[i].weight] + items[i].value > dp[j]) {
dp[j] = dp[j - items[i].weight] + items[i].value;
}
}
}
}
int main() {
int n, W;
cin >> n >> W;
for (int i = 1; i <= n; ++i) {
cin >> items[i].weight >> items[i].value;
}
// 清空dp数组（显式初始化）
memset(dp, 0, sizeof(dp));
cout << "完全背包最大价值: ";
knapsack_complete(n, W);
cout << dp[W] << endl;
cout << "01背包最大价值: ";
knapsack_01(n, W);
cout << dp[W] << endl;
return 0;
}
注释要点：
使用
items结构体提高可读性dp数组显式初始化为 0两种背包问题分别演示正序/逆序遍历
输入输出格式清晰
算法分析
时间复杂度：O(N×W)，N 是物品数，W 是背包容量
空间复杂度：O(W)，一维数组优化只需记录当前状态
常见误区：
完全背包误用逆序遍历（导致物品只能选一次）
忘记初始化
dp[0] = 0边界条件处理不当（如物品重量超过背包容量）
经典例题解析
例题1：P1060 [NOIP2005普及组] 采药
题意：给定预算和若干药材（每种最多选一次），求不超过预算的最大价值
关键点：
属于 01背包
需将重量和价值分开存储，注意输入顺序
例题2：P1048 [NOIP2006普及组] 开心的金明
题意：给定预算和若干物品（每种最多选一次），求不超过预算的最大价值
对比分析：
同属 01背包，但本题有额外约束条件（必须选至少一个物品）
需在 DP 后检查
dp[W]是否为 0
推荐练习
P1060 采药 （巩固 01背包）
P1079 [NOIP2004] 虫虫危机 （二维 DP 入门）
P1069 [NOIP2004] 细胞分裂 （状态压缩 DP 基础）
小结
动态规划的精髓是 “状态定义+转移方程”，记住两点：
状态要涵盖所有必要信息（如
dp[j]必须包含容量 j 的信息）转移要确保不漏解（背包问题需同时考虑不选/选当前物品的情况）
下期预告：树形 DP——解决树上路径问题的利器！