0

私はこの問題に取り組んできましたhttps://open.kattis.com/problems/walrusweights。他の誰かがここでそれについて尋ねているのを見ましたが、この問題に対する私のアプローチはまったく異なります.

この問題では、合計が 1000 に最も近い配列内の組み合わせを見つける必要があります。これが私の解決策です。時間制限 (0.26 秒、制限は 2 秒) でうまく機能しますが、31 個のテスト ケースの後、間違った結果になります。答え。

私のプログラムでは、最初にすべての数値を読み取り、配列サイズ n + 1 にします (最初の数値はゼロです。簡単に説明します)。次に、このメソッドを呼び出します。

public static void combination(int index, boolean use, int currentSum, int closest){
    HS.add(currentSum);
    HS.add(closest);
    if(index == size){
        return;
    }
    if(use)
        currentSum += array[index];
    index++;
    if(currentSum == 0){ //would interfere with the if statement below, if it's 0, it will always be closer to 1000 
        combination(index, true, currentSum, closest);
        combination(index, false, currentSum, closest);
    }
    else{
        if(Math.abs(1000 - currentSum) < Math.abs(1000 - closest)){//so, if the currentSum is closer to 1000 than the closest so far
            closest = currentSum; //this is now the closest one
        }
        else //otherwise, there's no point going on with further changes to this combination, it will never be closest
            return;
        combination(index, true, currentSum, closest);
        combination(index, false, currentSum, closest);
    }
}

と：

combination(0, nums, false, 0, 1000001); //limit of weights is 1000000

組み合わせメソッドでは、パラメーターは、現在のインデックス、配列、現在のエントリを合計に追加するかどうか、現在の合計、およびこれまでに 1000 に最も近い最高の組み合わせです。

すべての組み合わせが完了したら、1000 に最も近いものを取得する方法を作成しましたが、それが機能することは確かであり、非常に単純であるため、必要でない限り表示する価値はありません。

誰が私が間違っているのか教えてもらえますか? 組み合わせメソッドのロジックが間違っていますか、それとも余分なチェックや何か不足していますか?

4

1 に答える 1

0

少し遅れましたが、私はこれに答えました。他の人が必要かどうかを確認できるようにここに残します。

http://hastebin.com/etapohavud.cpp

数値の配列 (以前は並べ替え済み) をトラバースする再帰的なメソッドを作成し、最も近い数値につながる可能性のある合計のみをチェックし、可能なすべての数値を ArrayList に追加しました。それはソートされているので、私がチェックしている現在の合計全体を変更する可能性がある、より小さな数を先に見つけることを心配する必要はありません.

つまり、最終的に 1000 に最も近い実行可能な組み合わせをすべて計算し、それに最も近い組み合わせを見つけました。

于 2016-11-27T21:16:14.293 に答える