1

私は最初のプログラミングコースにいて、今かなり行き詰まっています。基本的に、テキスト ファイル (コードの 1 行目) から 16 個の値を取得し、コードの 2 行目に 1 つの値があります。これらの 16 個の値を配列に読み込み、その 2 行目の値をターゲットとして設定します。その部分については問題ありませんでした。

しかし、私が問題を抱えているのは、ビットマップを作成して、ターゲット数に等しい 16 の値のすべての可能なサブセットをテストすることです。

IE、これらの数値があったとします。

12   15   20   4   3   10   17   12   24   21   19   33   27   11   25   32

次に、各値をビットマップに対応させます

 0    1    1   0   0    0    0    1    1    1    0    1    0    0    1    0

次に、「1」で述語された値のみを受け入れます

     15   20                     12   24   21        33             25

次に、そのサブセットをテストして、「ターゲット」数と等しいかどうかを確認します。

問題で使用できる配列は 1 つだけで、数学クラスは使用できません (まだ取得していません)。

私は概念を理解しており、シフト演算子と論理記号を実装する必要があることを知っていますが、&本当に途方に暮れています。私はとてもイライラしていて、誰かが私に何かヒントをくれるかどうか疑問に思っていました.

4

5 に答える 5

0

OK、配列は 1 つだけ許可されます。おそらく、その配列は最初のデータセットを保持しています。したがって、アプローチに追加の配列を含める必要はありません。

この場合、ビットベクトルは単純なメンタル モデル構造です。アイデアは次のとおりです。考えられるすべての組み合わせ（順列ではないことに注意してください）を試すと、目標に最も近い合計が見つかります。N 個の数があるとしましょう。つまり、2^N可能な組み合わせがあるということです。

ビットベクトル アプローチでは、 to を使用して各組み合わせに番号を付け0、それぞれ2^N - 1を試します。

配列内の数値が 32 未満であると仮定すると、基本的に次のような外側のループがあります。

int numberOfCombinations = (1 << numbers.length - 1) - 1;
for (int i = 0; i < numberOfCombinations; ++i) { ... }

の各値について、 の各数値を調べて、 のシフトとビットマスクに基づいて追加またはスキップするかを決定するi必要があります。numbersi

于 2012-02-06T22:02:39.703 に答える
0

次のようなものが必要だと思います：

public boolean equalsTarget( int bitmap, int [] numbers, int target ) {
  int sum = 0; // this is the variable we're storing the running sum of our numbers
  int mask = 1; // this is the bitmask that we're using to query the bitmap
  for( int i = 0; i < numbers.length; i++ ) { // for each number in our array
    if( bitmap & mask > 0 ) { // test if the ith bit is 1
        sum += numbers[ i ]; // and add the ith number to the sum if it is
    } 
    mask <<= 1; // shift the mask bit left by 1
  }
  return sum == target; //if the sum equals the target, this bitmap is a match
}

コードの残りの部分は非常に単純です。ビットマップ (1..65535) のすべての可能な値をこのメソッドに入力し、結果を処理するだけです。

Ps: ソリューションを完全に理解していることを確認してください。ただコピーするだけではありません。:)

Pps:intこの場合、使用intは 32 ビット幅であり、必要なのは 16 ビットだけです。ただし、すべてのプリミティブ整数型 (byte、short、int、long) は Java で署名されているため、すべてのビットが必要な場合はビット演算に注意してください。 .

于 2012-02-06T22:23:20.163 に答える
0

これを解決するには、いくつかの手順があります。最初に、考えられるすべてのビットマップを列挙する必要があります。他の人が指摘したように、整数を 0 から 2^n - 1 にインクリメントすることで、これを簡単に行うことができます。

それができたら、可能なすべてのビットマップを反復処理して、そのビットマップを取得し、それを配列に「適用」して、マップによって表されるすべてのインデックスで要素の合計を生成する方法が必要です。次の方法は、その方法の例です。

private static int bitmapSum(int[] input, int bitmap) {
    // a variable for holding the running total
    int sum = 0;

    // iterate over each element in our array
    // adding only the values specified by the bitmap
    for (int i = 0; i < input.length; i++) {
        int mask = 1 << i;
        if ((bitmap & mask) != 0) {
            // If the index is part of the bitmap, add it to the total;
            sum += input[i];
        }
    }

    return sum;
}

この関数は、整数配列とビット マップ (整数として表される) を取り、インデックスがマスクに存在する配列内のすべての要素の合計を返します。

この関数の鍵は、特定のインデックスが実際にビットマップにあるかどうかを判断する機能です。これは、最初に目的のインデックスのビット マスクを作成し、次にそのマスクをビット マップに適用して、その値が設定されているかどうかをテストすることによって実現されます。

基本的に、1 ビットのみが設定され、他のすべてがゼロである整数を構築したいと考えています。次に、そのマスクをビットマップでビットごとに AND し、結果を 0 と比較して特定の位置が設定されているかどうかをテストできます。

次のような 8 ビット マップがあるとします。

map:       1 0 0 1 1 1 0 1
           ---------------
indexes:   7 6 5 4 3 2 1 0

インデックス 4 の値をテストするには、次のようなビット マスクが必要です。

mask:      0 0 0 1 0 0 0 0
           ---------------
indexes:   7 6 5 4 3 2 1 0

マスクを作成するには、1 から始めて N だけシフトします。

1:            0 0 0 0 0 0 0 1
shift by 1:   0 0 0 0 0 0 1 0
shift by 2:   0 0 0 0 0 1 0 0
shift by 3:   0 0 0 0 1 0 0 0
shift by 4:   0 0 0 1 0 0 0 0

これを取得したら、マスクをマップに適用して、値が設定されているかどうかを確認できます。

map:             1 0 0 1 1 1 0 1
mask:            0 0 0 1 0 0 0 0
                 ---------------
result of AND:   0 0 0 1 0 0 0 0

結果は != 0 なので、インデックス 4 がマップに含まれていることがわかります。

于 2012-02-06T22:44:40.780 に答える
0

int 内で可能なすべてのビット パターンを生成し、そのビット マップによって定義されるすべての可能なサブセットを生成するには、単に int を 1 から開始し、unsigned short int が保持できる最大値 (すべて 1) までインクリメントし続ける必要があります。各内部ループの最後で、合計をターゲットと比較します。一致する場合は、ソリューションのサブセットを取得しました - それを印刷してください。そうでない場合は、次のサブセットを試してください。誰かがこれを行う方法を説明するのを手伝ってもらえますか? 概念は理解できますが、それを実装する方法についての知識が不足しています。

于 2012-02-06T21:46:32.997 に答える