2

初心者向けにタイトルをわかりやすく説明します。私の問題は一般的な問題と非常によく似ています。整数配列の問題のすべての順列を見つけます。

整数のリストとターゲット番号を指定して、リストから番号の任意の組み合わせを選択して、それらの合計がターゲットと一致するかどうかを調べようとしています。関数型プログラミングの手法を使用して実行する必要があります。つまり、すべてのループとミューテーションが実行され、巧妙な再帰のみが実行されます。完全開示：これは宿題であり、メソッドヘッダーは教授によってそのまま設定されます。これは私が持っているものです：

public static Integer sum(final List<Integer> values) {
     if(values.isEmpty() || values == null) {
             return 0;
     }
     else {
             return values.get(0) + sum(values.subList(1, values.size()));
     }
 }

public static boolean groupExists(final List<Integer> numbers, final int target) {
     if(numbers == null || numbers.isEmpty()) {
             return false;
     }
     if(numbers.contains(target)) {
             return true;
     }
      if(sum(numbers) == target) {
              return true;
      }
      else {
              groupExists(numbers.subList(1, numbers.size()), target);
              return false;
      }
  }

sumメソッドがテストされ、機能しています。groupExistsメソッドが私が取り組んでいるメソッドです。リスト[1,2,3,4]を指定すると、3や10などのターゲットではtrueが返されますが、6ではfalseが返されます。これは、1,2,3が正しいため、混乱します。そして6に追加します。明らかに何かが欠けています。また、私が見ている主な問題は、すべての可能な組み合わせをテストしていないことです。たとえば、最初と最後の数字が可能性として足し合わされていないなどです。

更新：サイモンの答えに基づいて少し働いた後、これは私が見ているものです：

public static boolean groupExists(final List<Integer> numbers, final int target) {
     if(numbers == null || numbers.isEmpty()) {
             return false;
      }
     if(numbers.isEmpty()) {
              return false;
      }
      if(numbers.contains(target)) {
              return true;
      }
      if(sum(numbers.subList(1, numbers.size())) == (target - numbers.get(0))) {
              return true; }                                                                                                                                                                                                     
      else {
              return groupExists(numbers.subList(1, numbers.size()), target);
      }
  }
4

4 に答える 4

1

すべての組み合わせをチェックすることは階乗です（実装には少し欠けています）。別の（動的な）アプローチを試してみませんか。プログラミングコンテストのヒッチハイカーガイド、1ページ（サブセット和）を参照してください。

主な方法は次のようになります。

boolean canSum(numbers, target) {
  return computeVector(numbers)[target]
}

computeVectorのセットと合計できるすべての数値を含むベクトルを返しますnumbers。この方法computeVectorは再帰的に行うのが少し難しいですが、次のようなことができます。

boolean[] computeVector(numbers, vector) {
  if numbers is empty:
    return vector

  addNumber(numbers[0], vector)

  return computeVector(tail(numbers), vector);
}

addNumberベクトルを取り、新しい「実行可能な」数値で「埋める」（説明についてはヒッチハイカーを参照）。addNumberまた、少し注意が必要な場合もあります。お任せします。基本的に、次のループを再帰的に記述する必要があります。

for(j=M; j>=a[i]; j--)
  m[j] |= m[j-a[i]];
于 2012-12-01T22:23:55.943 に答える
1

n数、、、...、がありa[0]、サブセットの合計が。であるかどうかを調べたいとします。a[1]a[n-1]N

そのようなサブセットがあるとします。現在、含まれている場合a[0]と含まれていない場合があります。含まれている場合は、合計が。になるa[1]、...のサブセットが存在する必要があります。そうでない場合は、合計が。になる、...のサブセットが存在します。a[n]N - a[0]a[1]a[n]N

これにより、再帰的なソリューションが実現します。

于 2012-12-01T22:37:29.443 に答える
1

便宜上、宣言する

static Integer head(final List<Integer> is) {
  return is == null || is.isEmpty()? null : is.get(0);
}
static List<Integer> tail(final List<Integer> is) {
  return is.size() < 2? null : is.subList(1, is.size());
}

次に、あなたの機能はこれです：

static boolean groupExists(final List<Integer> is, final int target) {
  return target == 0 || target > 0 && head(is) != null &&
       (groupExists(tail(is), target) || groupExists(tail(is), target-head(is)));
}

驚くことではありませんが、実際には、ベースケースと最終行を定期的にチェックします。ここで、左と右のオペランドは、それぞれヘッドを含むまたは含まない「グループ」を検索します。

私が書いた方法では、これらがすべて純粋関数であることが一目でわかりますが、これはJavaであり、FP言語ではないため、この書き方はまったく最適ではありません。複数回発生する関数呼び出しを最終的なローカル変数にキャッシュすることをお勧めします。もちろん、それはまだ本によるでしょう。

于 2012-12-02T07:25:31.693 に答える
0

可能なすべての組み合わせのリストは、各再帰で非常に簡単な決定を行うことで到達できます。この組み合わせには私のリストの先頭が含まれていますか？あるかどうかのどちらかなので、各段階に2つのパスがあります。どちらかのパスが解決策につながる場合は、trueを返します。

boolean combination(targetList, sourceList, target)
{
    if ( sourceList.isEmpty() ) {
        return sum(targetList) == target;
    } else {
        head = sourceList.pop();
        without = combination(targetList, sourceList, target); // without head
        targetList.push(head);
        with = combination(targetList, sourceList, target); // with head
        return with || without;
    }
}
于 2012-12-01T22:55:05.967 に答える