1

この再帰的なバックトラッキングの問題に問題があります。

「整数のリストをパラメーターとして受け取り、再帰的なバックトラッキングを使用して、リストを等しい合計の2つのサブリストに分割できるかどうかを検出するパーティション化可能なメソッドを記述します。指定されたリストを均等に分割できる場合、メソッドはtrueを返す必要があります。そうでない場合はfalse。」

たとえば、リスト[1、2、3]をサブリスト[1、2]、および[3]に分割できるため、「true」の結果が生成されます。

私の解決策は正しいようですが、何があってもfalseを返します。理由がわかりません。

public static boolean partitionable(List<Integer> list1) {
        List<Integer> list2 = new ArrayList<Integer>();
        return partitionable(list1, list2);
    }

public static boolean partitionable(List<Integer> list1, List<Integer> list2) {
    boolean finalAnswer = false;
    int sum1 = 0;
    int sum2 = 0;
    for (int i = 0; i < list1.size(); i++) {
        sum1 += list1.get(i);
    }
    for (int i = 0; i < list2.size(); i++) {
        sum2 += list2.get(i);
    }
    if (sum1 == sum2) {
        return true;
    } else {
        for (int i = 0; i < list1.size() - 1; i++) {
            int number = list1.remove(i);
            list2.add(number);
            finalAnswer = partitionable(list1, list2);
            list2.remove(list2.size() - 1);
            list1.add(i, number);
        }
    }
    return finalAnswer;
}

編集：list1から要素を2回削除する問題を修正しました。

4

4 に答える 4

4

list1.remove(i)あなたは二度電話しています。2つの数値を削除し、そのうちの1つだけを保存してに追加するため、アルゴリズムが混乱する可能性がありますlist2。

それでも機能しない場合は、list1に進む候補としての最後の要素を無視していることにも気づきましたlist2。これが発生するアルゴリズム的な理由はわかりません。ループ-1からを削除してみてください。for

于 2011-07-25T01:30:01.670 に答える
1

問題はlist1.remove(i)2回呼び出すことです。これは機能しません。

から2つの数値を削除しlist1、に保存している間、保存しているのlist2は1つだけです。

于 2011-07-25T01:30:31.913 に答える
1

再帰的なケース（elseブロック）は、かどうかを確認し、そうfinalAnswer == trueである場合はすぐに返す必要があります。それ以外の場合は、falseが返されるケースにスキップして、最終的には下部に返されます。

アイテムを2回削除しているので、それで問題全体が解決するわけではありませんlist1。両方を修正すると、正しい解決策が得られるはずです。

于 2011-07-25T01:31:25.000 に答える
0

あなたの質問に直接答えないことをお詫びしますが、提起された質問を理解するには別の答えが必要です。

元の質問はこれを尋ねます：
Your method should return true if the given list can be partitioned equally

そして、あなたは後でこれを主張します：
[1, 2, 3] can be partitioned into the sublists [1, 2] and [3], so it would produce a result of "true."

これは私には正しく鳴りません。適切な解決策（再帰的なバックトラッキング要件を一時的に無視する）は、整数要素の数をカウントして% 2返すことNOT resultでしょうか？

言い換えると：

List has three elements.  
Divide by 2, remainder 1.
Return 0, list is not equally dividable.

List has four elements.
Divide by 2, remainder 0.
Return 1, list is equally dividable.

質問をどこで誤解したか教えてください。

于 2011-07-25T01:38:42.940 に答える