如何解決「管理你的能量」？

Question

我在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是可以 通過管理實現的最大增益你那天的精力。

這個問題怎麼解決？我在想如果它可以通過動態編程來解決。任何線索？

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

想象一下，在每個活動中花費的能量作爲多維空間中的座標。想象一下，在多維空間中獲得的收益是點的溫度。 （將不可能的組合視爲零增益。）這樣可以減少「找到房間中最熱點」的問題。這很簡單 - 從任何地方開始（可能爲了簡單起見，從每項活動花費的能源開始，因爲至少保證這是合法的），繼續向任何方向移動使其更熱，並在沒有方向變得更熱時停止。

直覺上，在我看來你不能陷入局部最大值（因爲輸出是輸入的線性鉗位函數）。但是如果你擔心這個問題，當你停下來時，你可以隨意「踢你自己」，然後再試一次。如果您重複幾次，並在同一地點持續登陸，您可以合理地確信這是全球最大值。

要使用重力隱喻，本質上是將問題映射到空間。您將最佳解決方案映射到空間中的最低點。然後它就像倒底一樣簡單。