3

合計 540000 の数字のリストがあります。このリストを 3 つのリストに並べ替えて、それぞれ合計 180000 にしたいと思います。これを行うための最も効率的なプログラミング方法は何ですか?ライン？

4

5 に答える 5

1

ナップザック問題のバリエーションのように聞こえます。これらの数値のサイズと数を知ることは有用です - サイズに大きなばらつきがありますか、それともスケールがすべて似ていますか? それらはたくさんありますか (>1000)、それとも数個しかありませんか (<100)?

手っ取り早く汚い方法の 1 つは、それらをサイズ順に並べ替えて (最大から最小)、ループして、最初のリストを最初のリストに、2 番目を 2 番目のリストに、3 番目を 3 番目のリストに入れ、そして戻って、 4番目を最初のリストに入れます...など。多くの小さな数字に対してはうまくいくかもしれません...しかし、データセットのさまざまなタイプに対する他のアプローチがあります。

于 2009-11-06T10:46:30.537 に答える
0

私はあなたのためにほとんどの仕事をするためにいくつかのJavaコードを書きました。

小さい方のメソッドは、達成される数値と合計のリストを取り、その合計を合計した数値のリストのセットを返します。あなたは18000とあなたの番号のリストでそれを実行することができます。

返された番号のリストごとに、すでに使用されている番号が欠落している新しいリストを作成し、18000以降でメソッドを再度実行する必要があります。

この2回目の呼び出しで1つ以上のリストが返される場合、残りの数も合計で18000になるため、問題は解決可能であることがわかります。

とにかく、ここにコードがあります。はい、それは単なる再帰的なブルートフォースです。他の方法で一貫して改善できる実証済みの方法がない可能性が非常に高いです。それが長時間実行されても私を責めないでください。最初に小さな例で試してみることをお勧めします。

import java.util.*; 

public class Listen {

   private static Set<List<Integer>> makeFrom(int total, List<Integer> numbers) {
      Set<List<Integer>> results = new HashSet<List<Integer>>();
      List<Integer> soFar = new ArrayList<Integer>();
      makeFrom(results, total, soFar, numbers, 0);
      return results;
   }

   private static void makeFrom(Set<List<Integer>> results, int total, List<Integer> soFar, List<Integer> numbers, int startingAt) {
      if (startingAt >= numbers.size()) return;
      for (int p=startingAt; p<numbers.size(); p++) {
         Integer number = numbers.get(p);
         List<Integer> newSoFar = new ArrayList<Integer>(soFar);
         newSoFar.add(number);
         int newTotal = total - number;
         if (newTotal < 0) continue;
         if (newTotal == 0) {
            Collections.sort(newSoFar);
            results.add(newSoFar);
         } else {
            List<Integer> newNumbers = new ArrayList<Integer>(numbers);
            newNumbers.remove(number);
            makeFrom(results, newTotal, newSoFar, newNumbers, startingAt + 1);
         }
      }
   }

   public static void main(String[] args) {
      List<Integer> numbers = new ArrayList<Integer>();
      for (int j=1; j<11; j++) numbers.add(j);
      for (List<Integer> result : makeFrom(25, numbers)) {
         System.out.println(Arrays.deepToString(result.toArray(new Integer[result.size()])));
      }
   }
}
于 2009-11-06T13:08:23.473 に答える
0

これにはNP 困難の匂いがします。その場合、それを行う「効率的な」方法はありません。おそらく、それにうまく取り組むことができるヒューリスティックをいくつでも思いつくことができますが.

[179998、180001、180001] のようなリストにはまだ問題があると言っていました:)

于 2009-11-06T10:59:43.467 に答える
0 
for i as integer = 1 to 180000
put data in array 1
next i

for i as integer = 180001 to 360000
put data in array 2
next i

for i as integer = 360001 to 540000
put data in array 3
next i
于 2009-11-06T10:37:52.800 に答える