6

Greplin チャレンジのレベル 3 で苦労しています。なじみのない人のために、ここに問題があります：

最大数が残りの数の合計である配列のすべてのサブセットを見つける必要があります。たとえば、次の入力の場合:

(1、2、3、4、6)

サブセットは

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

コードを実行する必要がある番号のリストを次に示します。パスワードはサブセットの数です。上記の場合、答えは 4 になります。

3、4、9、14、15、19、28、37、47、50、54、56、59、61、70、73、78、81、92、95、97、99

400 万以上の 22 の数字の組み合わせをすべて構築し、それらすべてをテストして正しい答えを得るソリューションをコーディングすることができました。問題は、クランチするのに40分以上かかることです. Web を検索すると、これに対する答えを 1 秒もかからずに得るアルゴリズムを作成できた人が何人かいるようです。計算コストの高い総当たり法よりも、これに取り組むためのより良い方法を疑似コードで説明できる人はいますか? それは私を夢中にさせています！

4

7 に答える 7

6

秘訣は、物事を行う方法がいくつあるかを追跡するだけでよいということです。数字はソートされて正であるため、これは非常に簡単です。これが効率的な解決策です。（私のラップトップでは0.03秒未満かかります。）

#! /usr/bin/python

numbers = [
    3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56,
    59, 61, 70, 73, 78, 81, 92, 95, 97, 99]

max_number = max(numbers)
counts = {0: 1}
answer = 0
for number in numbers:
    if number in counts:
        answer += counts[number]
    prev = [(s,c) for (s, c) in counts.iteritems()]
    for (s, c) in prev:
        val = s+number;
        if max_number < val:
            continue
        if val not in counts:
            counts[val] = c
        else:
            counts[val] += c
print answer
于 2011-06-15T06:44:26.187 に答える
3

値がゼロ以外であり、左から右に単調に増加することがわかっています。

考えられる合計（任意の順序、左から右で問題ありません）を列挙してから、その値の左側のサブセットを列挙します。これは、右側の値が参加できない可能性があるためです（合計も作成されます）。大きい）。セットをインスタンス化する必要はありません。各値を検討するのと同じように、ifが合計にどのように影響するかを確認してください。大きすぎる（その値を無視する、セットに含めることはできない）、適切な（セットの最後のメンバー）、または小さすぎる（その時点でセットに含まれる場合と含まれない場合があります）のいずれかです。

[この問題により、私は初めてPythonを試してみました。楽しい。]

これがPythonコードです。Cprofile.runによると、これは私のP87002.54Ghzラップトップでは.00772秒かかります。

values = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]

def count():
   # sort(values) # force strictly increasing order
   last_value=-1
   duplicates=0
   totalsets=0
   for sum_value in values: # enumerate sum values
      if last_value==sum_value: duplicates+=1
      last_value=sum_value
      totalsets+=ways_to_sum(sum_value,0) # faster, uses monotonicity of values
   return totalsets-len(values)+duplicates

def ways_to_sum(sum,member_index):
   value=values[member_index]
   if sum<value:
      return 0
   if sum>value:
      return ways_to_sum(sum-value,member_index+1)+ways_to_sum(sum,member_index+1)
   return 1

結果として得られるカウントは179です。（別のポスターの結果と一致します。）

編集：ways_to_sumは、末尾再帰ループを使用して部分的に実装できます。

def ways_to_sum(sum,member_index):
   c=0
   while True:
      value=values[member_index]
      if sum<value: return c
      if sum==value: return c+1
      member_index+=1
      c+=ways_to_sum(sum-value,member_index)

これは実行に.005804秒かかります：-}同じ答え。

于 2011-06-15T05:24:29.327 に答える
2

これは5ms未満で実行されます（python）。これは、メモ化された再帰と呼ばれる動的プログラミングの変形を使用します。この関数は、最初の要素goのサブセットの数を計算しました。合計は。になります。リストは並べ替えられているため、要素ごとに（as ）関数を1回呼び出して、結果を合計するだけで十分です。p+1targettarget

startTime = datetime.now()
li = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]
memo = {}
def go(p, target):
    if (p, target) not in memo:
        if p == 0:
            if target == li[0]:
                memo[(p,target)] = 1
            else:
                memo[(p,target)] = 0
        else:
            c = 0       
            if li[p] == target: c = 1
            elif li[p] < target: c = go(p-1,target-li[p])
            c += go(p-1, target)
            memo[(p,target)] = c
    return memo[(p,target)]

ans = 0
for p in range(1, len(li)):
    ans += go(p-1, li[p])

print(ans)
print(datetime.now()-startTime)
于 2011-06-15T06:43:27.980 に答える
1

これは動作します

public class A {

  static int[] a = {3,4,9,14,15,19,28,37,47,50,54,56,59,61,70,73,78,81,92,95,97,99};

  public static void main(String[] args) {
    List<Integer> b = new ArrayList<Integer>();

    int count = 0;
    for (int i = 0; i < a.length; i++) {
        System.out.println(b);
        for (Integer t:b) {
        if(a[i]==t)
        {
        System.out.println(a[i]);
            count++;
            }
        }

        int size = b.size();
        for (int j = 0; j < size; j++) {
        if(b.get(j) + a[i] <=99)
            b.add(b.get(j) + a[i]);
        }
            b.add(a[i]);
    }

    System.out.println(count);

  }
}

擬似コード（説明付き）：

  1. 次の変数を格納します

    i。）これまでのサブセットの「カウント」

    ii。）すべての可能なサブセットの合計を含む配列b

    2.アレイを反復処理します（たとえばa）。各要素についてa[i]

    i。）配列bを調べて、a[i]の出現回数を数えます。これを「カウント」に追加します

    ii。）配列bを調べ、各要素についてb [j] .add（a [i] + b [j]）をbに追加します。これは、サブセット和の可能性があるためです。（aのa [i] + b [j]> max要素の場合、uはそれを追加するために無視できます）

    iii。）a[i]をbに追加します。

3.uカウントがあります:)

于 2012-09-12T19:41:57.713 に答える
0

ここで入手できる Java のコンビネーション ジェネレーター クラスを使用しました。

http://www.merriampark.com/comb.htm

コンボを反復して有効なサブセットを探すのに 1 秒もかかりませんでした。(外部コードを使用することはこの課題に沿っているとは思いませんが、私も応募しませんでした。)

于 2011-06-15T05:09:01.760 に答える
0 
public class Solution {

   public static void main(String arg[]) {
    int[] array = { 3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61,
        70, 73, 78, 81, 92, 95, 97, 99 };
    int N = array.length;
    System.out.println(N);
    int count = 0;
    for (int i = 1; i < 1 << N; i++) {
        int sum = 0;
        int max = 0;
        for (int j = 0; j < N; j++) {
        if (((i >> j) & 1) == 1) {
            sum += array[j];
            max = array[j];
        }
        }
        if (sum == 2 * max)
        count++;
    }
    System.out.println(count);
    }

    public static boolean isP(int N) {
    for (int i = 3; i <= (int) Math.sqrt(1.0 * N); i++) {
        if (N % i == 0) {
        System.out.println(i);
        // return false;
        }
    }
    return true;
    }
}

役に立てば幸いですが、コピーして貼り付けるだけではいけません。

于 2012-10-09T21:19:25.850 に答える