01背包 · 动态演示（核心代码+原理）

▶ 📖 问题描述 & 算法原理

01背包问题：有 N 件物品和一个容量为 C 的背包。每件物品有重量 w[i] 和价值 v[i]，每件物品只能选择 0 或 1 次（即要么装入，要么不装）。求在不超过背包容量的前提下，能获得的最大总价值。

输入格式：
第一行：N C
接下来 N 行：w v

示例输入（5件）：
5 10
2 6
5 3
4 5
2 4
3 6
示例输出： 17

📌 算法原理

状态定义（一维DP）： dp[j] 表示容量为 j 时能获得的最大价值。

转移方程：
dp[j] = max(dp[j], dp[j - w[i]] + v[i]) （j 从 C 递减到 w[i]）

⚠️ 为什么容量要逆序枚举（从大到小）？
因为每个物品只能用一次，逆序保证了 dp[j - w[i]] 是上一轮（未选当前物品）的状态，从而避免同一物品被多次放入。

若容量正序枚举，会导致完全背包的效果（物品可重复使用）。

🎒 01背包 · 动态演示