题意分析

在最近新出了一款放置类游戏,名为《点击英雄》。游戏中用玩家可以消耗金币去升级英雄,击败怪物,获取更多的金币。英雄最开始的等级为0,不提供任何伤害,当玩家对英雄进行升级后,英雄获得等级x初始伤害的秒伤。英雄每一次升级花费的金币时前一次升级的1.07倍(下取整)。现在对于给定的英雄列表(当前均为0级),和玩家持有的金币数量M,我们想知道怎样分配金币去升级英雄,可以使得所有英雄的总秒伤之和达到最大。

可以点击这里在HihoCoder提交该题目

算法分析

本题为一道典型的泛化物品背包问题。泛化物品是背包问题的一个变种,要明白它,我们首先来回忆一下背包问题。

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 .. n
    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[n][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..25 && v ≥ c[ lvl ])

代码为:

for i = 1 .. n
    for v = 0 .. V
        f[i][v] = max(f[i][v], f[i - 1][v]);    // 假设不升级第i个英雄
        for c = 1 .. k
            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%。

可能是因为选手在平时的练习中没有遇到过这一类扩展背包问题,也没能在现场想出如何求解的算法。

背包问题在动态规划问题中算是经典问题,因此在这里推荐一篇讲解背包问题的文章,希望能够帮助大家。

本文由HihoCoder授权转载,原文链接

登录发表评论 注册

反馈意见