0

我在 Google Code Jam 中读到了一个关于能量的优化问题。（比赛已经结束了，可以聊聊了）

你今天的日历很忙，有很多重要的事情要做。您努力准备并确保所有活动不重叠。现在是早晨，您担心尽管您充满热情，但您将没有精力全神贯注地完成所有这些工作。

你必须小心管理你的能量。您开始充满活力的一天 - 准确地说是 E 焦耳的能量。你知道你不能低于零焦耳，否则你会筋疲力尽。您可以在每项活动上花费任何非负整数焦耳（如果您感到懒惰，您可以花费零），并且在每次活动后您将重新获得 R 焦耳的能量。然而，无论你多么懒惰，你在任何时候都不能拥有超过 E 焦耳的能量；超过那个点，你重新获得的任何额外能量都被浪费了。

现在，有些事情（比如解决 Code Jam 问题）比其他事情更重要。对于第 i 个活动，您有一个值 vi，表示该活动对您的重要性。您从每项活动中获得的收益是该活动的价值乘以您在该活动上花费的能量（以焦耳为单位）。你想管理你的能量，使你的总收益尽可能大。

请注意，您不能对日历中的活动重新排序。你只需要尽可能地使用你拥有的日历来管理你的能量。

输入

输入的第一行给出了测试用例的数量，T.T 测试用例紧随其后。每个测试用例由两行描述。第一个包含三个整数：E，最大（和初始）能量，R，每次活动后恢复的量，N，当天计划的活动数量。第二行包含 N 个整数 vi，描述你今天计划的活动的价值。

输出

对于每个测试用例，输出一行包含“Case #x: y”，其中 x 是案例编号（从 1 开始），y 是您通过管理当天的能量可以获得的最大收益。

如何解决这个问题？我在想它是否可以通过动态编程来解决。有什么线索吗？

4

2 回答 2

1

它可以简单地通过递归来完成，代码附在下面：这里的状态是 v 的数组，如问题

    public static long calculate(long limit,long initialEnergy,long R,long[] status,int start){
    long leftEnergy = 0;
    long  maxGain = 0;
    if(start + 1 > status.length){
        return  0;
    }
    for(long taskEnergy = initialEnergy; taskEnergy>=0;taskEnergy--){
        leftEnergy = initialEnergy - taskEnergy + R;
        if(leftEnergy > limit){
            leftEnergy = limit;
        }
        long gain = status[start] * taskEnergy + calculate(limit,leftEnergy, R, status, start +1);
        if(gain > maxGain){
            maxGain = gain;
        }
    }
    //System.out.println(start + " " +  maxGain);
    return maxGain;
}
于 2013-04-27T07:04:27.397 回答
-1

将花费在每个活动上的能量想象为多维空间中的坐标。想象一下作为该多维空间中点的温度所获得的增益。（将不可能的组合视为增益为零。）这减少了“找到房间中最热点”的问题。这很容易——从任何地方开始（可能，为简单起见，从每项活动花费的能量为零开始，因为至少可以保证这是合法的），继续朝任何让它变得更热的方向移动，并在没有方向让它变得更热时停止。

直观地说，在我看来，你不能陷入局部最大值（因为输出是输入的线性、钳位函数）。但如果你担心它，当你停下来的时候，向一个随机的方向“踢自己”，然后再试一次。如果您重复几次并始终落在同一个位置，您可以有理由相信这是全局最大值。

要使用重力隐喻，本质上是将问题映射到空间。您将最佳解决方案映射到空间中的最低点。然后就像跌到谷底一样容易。

于 2013-04-27T04:21:50.573 回答