0

Google Code Jam でエネルギーに関する最適化問題を読みました。（コンテストはもう終わったので、話しても大丈夫です）

今日の予定表は非常に忙しく、やらなければならない重要なことでいっぱいです。すべての活動が重複しないように準備し、確認するために一生懸命働きました。今朝、あなたは熱意にもかかわらず、これらすべてを全力で行うエネルギーがないのではないかと心配しています.

エネルギーを注意深く管理する必要があります。あなたはエネルギーに満ちた一日を始めます - 正確には E ジュールのエネルギーです。ゼロ ジュールを下回ることはできません。各アクティビティには、負でない整数のジュールを使用できます (怠惰な場合はゼロを使用できます)。各アクティビティの後、R ジュールのエネルギーが回復します。しかし、どんなに怠け者でも、いつでも E ジュール以上のエネルギーを持つことはできません。その時点を過ぎて回復する余分なエネルギーは無駄になります。

さて、いくつかのこと (Code Jam の問題の解決など) は他のことよりも重要です。i 番目の活動については、この活動があなたにとってどれほど重要であるかを表す値 vi があります。各アクティビティから得られるゲインは、アクティビティの値に、アクティビティに費やしたエネルギー量 (ジュール単位) を掛けたものです。あなたは自分のエネルギーを管理して、総利得ができるだけ大きくなるようにしたいと考えています。

カレンダーの活動を並べ替えることができないことに注意してください。あなたが持っているカレンダーでできる限り自分のエネルギーを管理しなければなりません。

入力

入力の最初の行は、テスト ケースの数 T を示します。T テスト ケースが続きます。各テスト ケースは 2 行で記述されます。最初の値には 3 つの整数が含まれます。E は最大 (および初期) のエネルギー量、R は各アクティビティの後に回復する量、N は 1 日に予定されているアクティビティの数です。2 行目には、今日計画した活動の値を表す N 個の整数 vi が含まれています。

出力

テスト ケースごとに、"Case #x: y" を含む 1 行を出力します。ここで、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 に答える