题意分析
在最近新出了一款放置类游戏,名为《点击英雄》。游戏中用玩家可以消耗金币去升级英雄,击败怪物,获取更多的金币。英雄最开始的等级为0,不提供任何伤害,当玩家对英雄进行升级后,英雄获得等级x初始伤害的秒伤。英雄每一次升级花费的金币时前一次升级的1.07倍(下取整)。现在对于给定的英雄列表(当前均为0级),和玩家持有的金币数量M,我们想知道怎样分配金币去升级英雄,可以使得所有英雄的总秒伤之和达到最大。
算法分析
本题为一道典型的泛化物品背包问题。泛化物品是背包问题的一个变种,要明白它,我们首先来回忆一下背包问题。
01背包问题
给定 n 个物品,每个物品具有
c[i]
的体积和w[i]
的价值。我们现在有一个大小为 V 的背包,每个物品要么放进背包,要么不放进背包。
问如何放置可以使得背包内的物品价值总最大,且总体积不超过 V 。
一个暴力的算法是枚举每一件物品是否在包内,总共有 2^n 种不同的组合方案。检查每一种方案是否合法以及计算其价值需要花费 O(n) 的时间。所以该算法总时间复杂度为 O(2^n*n) 。
显然暴力算法是不可行的。
通过对原问题的分析,我们得到一个结论:放置一个物品时,并不会对之前的放置结果产生影响。
由此得到一个递推公式,假设f[i][v]
表示放置前i
件物品,且总体积为v
时的最优价值,则有:
f[i][v] = max{f[i - 1][v], f[i - 1][ v - c[i] ] + w[i]} (v ≥ c[i])
若从f[i - 1][v]
转移,则表示不将第i
件物品放入背包;若从f[i - 1][ v - c[i] ] + w[i]
转移,则表示将第i
件物品放入背包。
其代码:
for i = 1 .. n
for v = 0 .. V
f[i][v] = max(f[i - 1][v], f[i - 1][ v - c[i] ] + w[i])
边界条件为f[0][0..V] = 0
,最后的答案为max{f[n][0..V]}
。
对于01背包问题,其算法时间复杂度为 O(nV) 。
分组背包问题
给定 n 个物品,每个物品具有
c[i]
的体积和w[i]
的价值。我们现在有一个大小为 V 的背包,每个物品要么放进背包,要么不放进背包。
此外,我们将这 n 个物品分为了 k 组,每一组至多只能有一个物品在背包中。
比如物品
i
和物品j
同属于一个分组,那么物品i
和物品j
不能同时放入背包,即使背包能够同时装下它们。问如何放置可以使得背包内的物品价值最大,且体积不超过 V 。
此时放置物品的限制变成了要么选择一组中的一件,要么一件都不放置。
我们简单的对原来的数组进行改进,f[i][v]
表示放置前i
组物品,且总体积为v
时的最优价值。显然,仍然有:
f[i][v] = max{f[i - 1][v], f[i - 1][ v - c[i] ] + w[i]} (v ≥ 0)
但跟原来方程不同的是,此处的c[i]
和w[i]
不再是单个物品i
的价值。而其对应的含义为,在第i
组物品中选取一个体积为c[i]
的物品,其对应的价值为w[i]
。因此我们需要枚举我们选取的是哪一个物品,所以该式子改变为:
f[i][v] = max{f[i - 1][v], f[i - 1][ v - c[t] ] + w[t]} (v ≥ c[t] && t ∈ group[i])
代码为:
for i = 1 .. k
for v = 0 .. V
f[i][v] = max(f[i][v], f[i - 1][v]); // 假设不放置第i组的物品
for t in group[i]
f[i][v] = max(f[i][v], f[i - 1][ v - c[t] ] + w[t]);
同样的,边界条件为f[0][0..V] = 0
,最后的答案为max{f[k][0..V]}
。
对于分组背包问题,其算法时间复杂度仍然为 O(nV) 。
泛化物品背包问题
给定 n 个物品,每个物品可以任意改变其体积
c[i]
。当物品i
的体积为c[i]
时,产生的价值为f_i(c[i])
。我们现在有一个大小为 V 的背包,每个物品要么放进背包,要么不放进背包。
问如何放置可以使得背包内的物品价值最大,且体积不超过 V 。
泛化物品背包问题本质就是分组背包问题。
每个物品根据体积不同,对应的价值不同。这里的一个物品实际等价与一组物品,而该组物品包含的物品数量为无穷多,且刚好满足体积从0到无穷。
即对应任意一个 c 都可以从该组中找到体积为 c 的物品。
所以我们可以得到递推公式:
f[i][v] = max{f[i - 1][v], f[i - 1][ v - c ] + f_i(c)} (c = 0..v)
代码为:
for i = 1 .. n
for v = 0 .. V
f[i][v] = max(f[i][v], f[i - 1][v]); // 假设不放置第i组的物品
for c = 0 .. v
f[i][v] = max(f[i][v], f[i - 1][ v - c ] + f_i(c));
同样的,边界条件还是为f[0][0..V] = 0
,最后的答案为max{f[n][0..V]}
。
对于泛化物品背包问题,其算法时间复杂度为 O(nV^2) 。
到此再回过头来看看我们的题目,其如何转化为一个泛化物品背包问题呢?
- n : n 个不同的英雄
- V : 我们持有的金币数量
- c : 英雄升级所消耗的费用
- w : 英雄所产生的DPS
在以上4个基础变量的基础上,我们还需要增加一个:
- lvl : 英雄选择提升的等级
那么我们可以得到:
c[ lvl ]
: 英雄等级为lvl
时所消耗的金币数量w[ lvl ]
: 英雄等级为lvl
时所产生的DPS
进一步得到我们的递推方程:
f[i][v] = max{f[i - 1][v], f[i - 1][ v - c[ lvl ] ] + w[ lvl ]} (lvl = 0,1,2... && v ≥ c[ lvl ])
代码为:
for i = 1 .. n
for v = 0 .. V
f[i][v] = max(f[i][v], f[i - 1][v]); // 假设不升级第i个英雄
for lvl = 1 .. MAX_POSSIBLE_LVL
if (v >= c[ lvl ])
f[i][v] = max(f[i][v], f[i - 1][ v - c[ lvl ] ] + w[ lvl ]);
当然,我们需要预处理出每一个英雄的c[ lvl ]
和w[ lvl ]
数组。
至此我们还需要担心一个问题:lvl
最大可能的取值为多少?
假设存在一个英雄其从0级升级到1级所需要的金币为1,则他最多可能升级的次数是:
log(20000) / log(1.07) = 146.37430359503807837404969001237
因此 lvl 最大的可能取值为146
。
但由于 n 的范围很小,这样的数据范围是可以接受的。
结果分析
该题在本次比赛中通过率只有8%。
可能是因为选手在平时的练习中没有遇到过这一类扩展背包问题,也没能在现场想出如何求解的算法。
背包问题在动态规划问题中算是经典问题,因此在这里推荐一篇讲解背包问题的文章,希望能够帮助大家。
有个疑问希望大神解答, [1.07...[1.07[1.07Bi]]...],当英雄从0级升到1级时花费金币1,按照每步都向下取整的说法,那么每次升级都只需要花费1金币,当有20000金币时最高级数应该是20000,而不是146啊?是我理解错了么,求解释。。。
@20111210 的分析是对的,146是不对的。
是要向下取整,其实没必要算这个最大值,只要超出钱数就break
这个最大值直接影响到程序的运行时间怎么可能不需要考虑最大值呢= =,可以超出钱数就break,但按照分析所说的那样写程序,肯定是有样例TLE的啊。。。。@june_启俊 题目分明说的“round down to the neareast integer”,这不是向下取整是四舍五入?@weidiao
146没错吧。这里的向下取整不是相对前一级的花费*1.07再向下取整,而是相对于基数*1.07^n之后再向下取整吧
根据题意 “So Raising ith hero from level X to level X+1 will cost [1.07...[1.07[1.07Bi]]...](repeat X times) coins where "[]" is the rounding function” 应该是相对前一级的花费*1.07再向下取整的