P5662 [CSP-J2019] 纪念品 分析

· · 个人记录

本题很明显是动态规划。

可以用完全背包的思路来做：每一件纪念品一天能买无数次，将背包容量设为当前拥有的金币数量，将体积设为今天的价值，将价值设为明天的价值。

这样使用完全背包即可。

为什么？因为题目中有比较重要的一条：当日买进的纪念品也可立马卖出。因此，我们可以将价值设为今天与明天的价格差。

于是转移方程就是：

f(i, j) = \max {f(i - 1, j - P_{i,j}) + P_{i+1,j} - P_{i, j}, f(i - 1, j)}

本题告诉了我们背包模型的常见：对于很多作出选择的动态规划，我们都可以将其归为 01 背包、完全背包或者多重背包的一种。重点在于怎么设出正确的状态，也即 容量、体积 与 价格。这三者缺一不可。

明显，体积和价格是每一个物品所具有的属性。体积是作出选择所要付出的代价，而价格是所能获得的利益。而容量是转移方程中所变化的量，容量的变化能够影响当前的决定。

根据这些量来将题目抽象化，就可能将难以解决的问题归为背包问题。