如何解决“管理你的精力”？

Question

我在Google中读到了一个关于能源的优化问题。(比赛现在结束了，所以可以讨论了)

你今天有个很忙的日历，满是重要的事情要做。你努力准备，确保所有的活动都不会重叠。现在已经是早上了，你担心，尽管你充满了热情，但你不会有足够的精力去做这一切。 你必须谨慎地管理你的精力。你开始了充满能量的一天--准确地说，是能量的焦耳。你知道你不能降到零焦耳以下，否则你就会精疲力竭。你可以在每个活动上花费任何非负的整数焦耳数(如果你觉得懒惰的话，你可以花费零)，在每次活动之后，你将重新获得R焦耳的能量。然而，无论你多么懒惰，你在任何时候都不能拥有超过E焦耳的能量；超过那个点的任何额外的能量都是浪费的。 现在，有些事情(比如解决代码阻塞问题)比其他事情更重要。对于ith活动，您有一个表示此活动对您有多重要的值vi。你从每个活动中得到的收益是活动的价值，乘以你花费在活动上的能量(以焦耳计)。你想要管理好你的能量，这样你的总收益就会尽可能大。 请注意，不能重新排序日历中的活动。你只需尽你所能管理好你的精力，用你的日历。 输入 输入的第一行给出了测试用例的数量，T测试用例紧随其后。每个测试用例由两行描述。第一个整数包含三个整数: E，最大(和初始)能量量，R，每次活动后您重新获得的数量，以及N，计划一天的活动数量。第二行包含N个整数vi，描述了您今天计划的活动的值。 输出 对于每个测试用例，输出一行包含“case #x: y"，其中x是用例数(从1开始)，y是通过管理当天的精力可以获得的最大收益。

如何解决这个问题呢？我在想是否可以用动态规划来解决这个问题。有什么线索吗？

Answer 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;
}

Answer 2

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

直觉上，在我看来，你似乎不能陷入局部最大值(因为输出是一个线性的，夹紧的输入函数)。但是如果你担心的话，当你停下来的时候，用一个随机的方向踢自己，然后再试一次。如果你重复了几次，并且不断地在同一地点降落，你就会有理由相信这是全球最大的。

从本质上说，要使用重力隐喻，您可以将问题映射到一个空间。您可以将最佳解决方案映射到空间中的最低点。那就像掉到谷底一样容易。