🎒 分组背包 · 动态演示 + 核心代码

📌 算法原理

状态定义： dp[i][j] 表示考虑前 i 组，背包容量为 j 时能获得的最大价值。

转移方程：
dp[i][j] = max( dp[i-1][j], max_{k∈组i} ( dp[i-1][j - w_{i,k}] + v_{i,k} ) )
即：不选第 i 组任何物品，或选该组内某个物品 k。

⚠️ 为什么枚举顺序是“组 → 容量 → 组内物品”？
• 组在外层：保证每组最多选一个，因为 dp[i][j] 只依赖 dp[i-1][...]，不会同组内多个物品叠加。
• 容量在中间：容量是背包的限制维度，需要遍历所有可能容量，以便后续组继承。
• 组内物品在最内层：在固定组和容量的前提下，枚举该组所有物品，取最大值，实现“组内最多选一个”的约束。

这种顺序确保了动态规划的无后效性和最优子结构。