Facebook黑客杯:权力压倒性

Question

Facebook上的很多人喜欢玩星际争霸II™.他们中的一些人使用星际争霸II™地图编辑器制作了一个自定义游戏.在这个游戏中,你扮演高贵的神族,从一个巨大的虫族军队中捍卫你收养的Shakuras家园.在被淹没之前,你必须尽可能多地对虫族造成伤害.你只能建造两种类型的单位,盾牌发电机和战士.盾牌发生器不会造成伤害,但是你的军队每生成一个盾牌发生器就可以存活一秒钟.勇士每秒造成一次伤害.盾牌发生器到期后,你的军队立即超支.你应该建造多少盾牌发生器和多少战士,以便在你的军队超支之前对虫族施加最大的伤害？因为Protoss重视勇敢,如果有多个解决方案,你应该返回使用最多战士的那个.

约束

• 1≤G(一个屏蔽发电机的成本)≤100
• 1≤W(一个战士的费用)≤100
• G +W≤M(可用资金)≤1000000000000(10 ¹²)

Answer 1

这是一个复杂度为O(W)的解决方案.设g是我们建造的发电机的数量,同样地让w为我们建造的战士数量(而G,W是每单位的相应价格).

我们注意到,我们要最大限度地提高w ^*G受到W*W + G*G <= M.

首先,我们将摆脱其中一个变量.请注意,如果我们选择g的值,那么显然我们应该尽可能多地购买剩余金额M-g*G的战士.换句话说,w = floor((Mg*G)/ W).

现在,问题是最大化g*floor((Mg*G)/ W)经受0 <= g <= floor(M/G).我们想摆脱这个问题,所以让我们考虑一下W的不同情况.让我们写g = W*k + r,其中0 <= r <W是将g除以W时的余数.

现在的想法是修复r,并插入g的表达式,然后让k成为等式中的变量.我们将在k中得到以下二次方程:

设p = floor((M-r*G)/ W),则方程为(-GW)*k ^ 2 +(Wp-rG)k + rp.

这是一个二次方程,当x变为无穷大或负无穷大时,它变为负无穷大,因此它在k = -B /(2A)时具有全局最大值.为了找到k的合法值的最大值,我们将尝试k的最小合法值,k的最大合法值以及实际最大值的两个最接近的整数点(如果它们在合法范围内).

r的所有值的总体最大值是我们正在寻找的值.由于r有W值,并且需要O(1)来计算固定值的最大值,因此总时间为O(W).

Answer 2

如果你制造g发电机和w战士,你可以造成w(每次伤害)× g(游戏结束时间)的总伤害 .

资金约束限制的值克和瓦特到W¯¯ × 瓦特 + G ^ × 克 ≤ 中号.

如果你建造g发电机,你可以建造最多(M - g × G)/ W战士,并做g ×(M - g × G)/ W伤害.

该函数在g = M /(2 G)时具有最大值,这导致M ² /(4 G W)损坏.

摘要:

• 构建M /(2 G)屏蔽发生器.
• 建立M /(2 G)战士.
• 造成M ² /(4 G W)伤害.

由于您只能构建两个单位中的任何一个的整数,这会减少优化问题:

最大化 克 × 瓦特
相对于 克 × G ^ + 瓦特 × w ^ ≤ 中号 和 克,瓦特 ∈ℤ ⁺

整数规划的一般问题是NP完全的,因此最好的算法是检查接近上述实值解的所有整数值.

如果发现某些对(克_我,瓦特_我),总损伤d _我,你只需要检查值,其中克_Ĵ × 瓦特_Ĵ ≥ d _我.这与原来的状态W¯¯ × 瓦特 + G ^ × 克 ≤ 中号约束与发现的每个项目的搜索空间.

F#-code:

let findBestSetup (G : int) (W : int) (M : int) =
    let mutable bestG = int (float M / (2.0 * float G))
    let mutable bestW = int (float M / (2.0 * float W))
    let mutable bestScore = bestG * bestW
    let maxW = (M + isqrt (M*M - 4 * bestScore * G * W)) / (2*G)
    let minW = (M - isqrt (M*M - 4 * bestScore * G * W)) / (2*G)
    for w = minW to maxW do
        // ceiling of (bestScore / w)
        let minG = (bestScore + w - 1) / w
        let maxG = (M - W*w)/G
        for g = minG to maxG do
            let score = g * w
            if score > bestScore || score = bestScore && w > bestW then
                bestG <- g
                bestW <- w
                bestScore <- score
    bestG, bestW, bestScore