2013-04-27 67 views
0

我在Google Code Jam中阅读optimisation problem about energy。 (现在比赛结束了,所以可以谈谈)如何解决“管理你的能量”?

今天你有一个非常繁忙的日历,充满了重要的事情要做。 您努力准备,并确保所有活动不重复 。现在是早上,你担心尽管你的热情很高,但你不会有精力去完成所有这些,并且完全参与 。

你将不得不小心管理你的能量。准确地说,你开始一天的能量 - E焦耳的能量,完整的 。你知道你不能在零焦以下去 ,否则你会因疲惫而下降。您可以在每项活动上花费任何 非负的整数焦耳(如果您觉得懒惰,您可以花费 为零),并且在每次活动之后,您将重新获得能量焦耳R 。然而,无论你多么懒惰,你在任何时候都不能有比能量高出几焦耳的能量;任何额外的能量,你会 重获过去那一点是浪费。

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

请注意,您无法重新排列日历中的活动。你只需要 必须管理你的能量以及你可以用你的日历 有。

输入

输入的第一行给出的测试用例的数量,T T检验 例遵循。每个测试用例由两行描述。第一个 包含三个整数:E,能量的最大(和最初)金额,R,您在每次活动后重新获得的金额,以及N,当天计划的活动数量。第二行包含N 整数vi,描述您今天计划的 活动的值。

输出

对于每一个测试的情况下,输出包含一个行“案例#X为:y”,其中x是 的情况下数(从1开始),而y是可以 通过管理实现的最大增益你那天的精力。

这个问题怎么解决?我在想如果它可以通过动态编程来解决。任何线索?

+0

是的!你不需要知道动态编程来解决这个问题,但它是一个明智的攻击线。任何时候做出最佳决定的理由都不取决于以前的决定,除非通过他们留给你的能量。这表明定义'f(n,e)'是n次活动之后的最优分数,给你留下e点能量。所以'f(0,e)= 0'。你可以用'f(n-1,?)'和'v_n'来表示'f(n,·)'的递归关系。原问题的答案是'max_e f(N,e)'。 – 2013-04-28 13:25:08

+0

感谢您编辑问题和重演。 – 2013-05-02 12:13:38

回答

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; 
} 
+0

很好的答案。十分优雅。你在比赛中解决了这个问题吗? – 2013-05-02 12:11:22

-1

想象一下,在每个活动中花费的能量作为多维空间中的坐标。想象一下,在多维空间中获得的收益是点的温度。 (将不可能的组合视为零增益。)这样可以减少“找到房间中最热点”的问题。这很简单 - 从任何地方开始(可能为了简单起见,从每项活动花费的能源开始,因为至少保证这是合法的),继续向任何方向移动使其更热,并在没有方向变得更热时停止。

直觉上,在我看来你不能陷入局部最大值(因为输出是输入的线性钳位函数)。但是如果你担心这个问题,当你停下来时,你可以随意“踢你自己”,然后再试一次。如果您重复几次,并在同一地点持续登陆,您可以合理地确信这是全球最大值。

要使用重力隐喻,本质上是将问题映射到空间。您将最佳解决方案映射到空间中的最低点。然后它就像倒底一样简单。