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

▶ 📖 问题描述 & 算法原理

完全背包问题：有 N 件物品（每种物品无限件）和一个容量为 C 的背包。每件物品有重量 w[i] 和价值 v[i]，每种物品可以取 任意非负整数件。求在不超过背包容量的前提下，能获得的最大总价值。

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

示例输入（5件）：
5 10
2 6
5 3
4 5
2 4
3 6
示例输出： 30（例如选5件物品1，重量10，价值30）

📌 算法原理

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

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

⚠️ 为什么容量要正序枚举（从小到大）？
因为每种物品可以无限次使用，正序允许 dp[j - w[i]] 已经被当前物品更新过，从而实现同一物品的多次放入。

若容量逆序枚举，则会退化为01背包（每种物品最多一次）。

♻️ 完全背包 · 动态演示