11

Java では、特定の値 K に最も近い (または等しい) 配列の要素の合計を見つけるにはどうすればよいですか?

たとえば、配列 {19,23,41,5,40,36} と K=44 の場合、可能な最も近い合計は 23+19=42 です。私はこれに何時間も苦労してきました。私は動的計画法についてほとんど何も知りません。ちなみに、配列には正の数しか含まれていません。

4

4 に答える 4

16

通常、このような問題には動的計画法を使用します。ただし、基本的には、次のコードのように、可能な合計のセットを保持し、入力値を 1 つずつ追加することになり、漸近的な実行時間は同じになりますO(n K)。ここnで、 は入力配列のサイズ、Kはターゲット値です。 .

ただし、以下のバージョンの定数はおそらく大きいですが、コードは動的プログラミングのバージョンよりもはるかに簡単に理解できると思います。

public class Test {
    public static void main(String[] args) {
        int K = 44;
        List<Integer> inputs = Arrays.asList(19,23,41,5,40,36);

        int opt = 0;                // optimal solution so far          

        Set<Integer> sums = new HashSet<>();
        sums.add(opt);

        // loop over all input values
        for (Integer input : inputs) {
            Set<Integer> newSums = new HashSet<>();

            // loop over all sums so far                        
            for (Integer sum : sums) {
                int newSum = sum + input;

                // ignore too big sums
                if (newSum <= K) {
                    newSums.add(newSum);

                    // update optimum                       
                    if (newSum > opt) {
                        opt = newSum;
                    }
                }
            }

            sums.addAll(newSums);
        }

        System.out.println(opt);
    }
}

編集

O(n K)正当な理由なしに主張しただけなので、実行時間に関する短いメモが役立つ場合があります。

明らかに、初期化と結果の出力には一定の時間がかかるため、二重ループを分析する必要があります。

外側のループはすべての入力に対して実行されるため、本体が実行されるn回数です。

内側のループはこれまでのすべての合計に対して実行され、理論的には指数数になる可能性があります。ただし、 の上限を使用するKため、 のすべての値sumsは範囲内にあります[0, K]。sumsはセットであるため、多くても要素を含みますK+1。

内側のループ内のすべての計算には一定の時間がかかるため、ループ全体の所要時間はO(K)です。同じ理由で、セットnewSumsには多くても要素が含まれているため、最終的には要素も含まれます。K+1addAllO(K)

まとめ: 外側のループはn回実行されます。ループ本体はO(K). したがって、アルゴリズムは で実行されO(n K)ます。

編集2

最適な合計につながる要素を見つける方法についてもリクエストに応じて:

単一の整数 (サブリストの合計) を追跡する代わりに、サブリスト自体も追跡する必要があります。新しい型を作成する場合、これは比較的簡単です (例を簡潔にするためにゲッター/セッターはありません)。

public class SubList {
    public int size;
    public List<Integer> subList;

    public SubList() {
        this(0, new ArrayList<>());
    }

    public SubList(int size, List<Integer> subList) {
        this.size = size;
        this.subList = subList;
    }
}

初期化は次のようになります。

SubList opt = new SubList();

Set<SubList> sums = new HashSet<>();
sums.add(opt);

の内側のループにsumsもいくつかの小さな調整が必要です。

for (Integer input : inputs) {
    Set<SubList> newSums = new HashSet<>();

    // loop over all sums so far                        
    for (SubList sum : sums) {
        List<Integer> newSubList = new ArrayList<>(sum.subList);
        newSubList.add(input);
        SubList newSum = new SubList(sum.size + input, newSubList);         

        // ignore too big sums
        if (newSum.size <= K) {
            newSums.add(newSum);

            // update optimum                       
            if (newSum.size > opt) {
                opt = newSum;
            }
        }
    }

    sums.addAll(newSums);
}
于 2013-04-15T19:14:52.510 に答える
0 
private int closestSum(int[] a, int num){
    int k=a.length-1;
    int sum=0;
    Arrays.sort(a);

    while(a[k]>num){
        k--;
    }
    for(int i=0;i<k;i++){
        for(int j=i+1;j<=k;j++){
            if(a[i]+a[j]<=num && a[i]+a[j]>sum)
                sum = a[i]+a[j];
        }
    }
    return sum;
}
于 2020-05-19T20:27:30.593 に答える