题目内容

塔子哥有$n$个魔法石，初始时魔法石的价值为$a_i$.塔子哥还有$m$点能量。对于每个能量，它可以用来点亮一颗魔法石。第$i$个魔法石第一次被点亮后的价值为$b_i$，魔法石也可以被再次点亮，价值进而变为$c_i$.请问塔子哥该如何安排手中的能量，使得魔法石的价值总和最大呢？

思路:动态规划-分组背包

本问题等价于 有一个容积为$m$的背包，现有$n$组物品，每组有三个物品，第$i$组物品为:

物品1:价值$a_i$,体积$0$

物品2:价值$b_i$,体积$1$

物品3:价值$c_i$,体积$2$