SubsetSum с использованием рекурсии и возврата - PullRequest
Новая
       123

SubsetSum с использованием рекурсии и возврата

0 голосов
/ 08 июля 2019

Я написал алгоритм, позволяющий определить, будет ли подмножество группы чисел суммироваться с заданной целью с помощью обратного отслеживания и рекурсии (возвращает true / false)

Пример: {5, 2, 3, 6} с Target = 8 ==> True || {5, 2, 3, 6} с целью = 20 ==> Ложь

Я хочу изменить свой алгоритм так, чтобы он включал все 5, которые могут присутствовать в наборе. Я испытываю трудности с тем, как это понять, используя возврат и рекурсию. Любой совет приветствуется

Пример: {5, 2, 3, 6} с целью 8 ==> True || {6, 2, 3, 5, 5} с целью 8 ==> Ложь

Я написал алгоритм, который рекурсивно включает число и проверяет сумму, а затем пропускает число из суммы, но я не знаю, как изменить свой алгоритм, чтобы выбрать только определенные числа и включить их в сумму 

public static void main(String argv[]) {
        int[] ints = { 10, 1, 3, 2 };
        int target = 5;
        int start = 0;
        System.out.println(groupSum(ints, target, 0, start));
    }

    public static boolean groupSum(int[] arr, int target, int sum, int start) {
        if (sum > target) {
            return false;
        }
        if (sum == target) {
            return true;
        }
        if (start >= arr.length) {
            return false;
        }
        //choose
        sum = sum + arr[start];
        //explore
        if (groupSum(arr, target, sum, start + 1))
            return true;
        //un-choose
        sum = sum - arr[start];
        return groupSum(arr, target, sum, start + 1);
    }

1 Ответ

2 голосов
/ 09 июля 2019

Заставьте его смотреть, включая 5, только если он его видит, и только проверять = sum в конце.Вот так: 

public static void main(String argv[]) {
    int[] ints = { 10, 1, 3, 2 };
    int target = 5;
    int start = 0;
    System.out.println(groupSum(ints, target, 0, start));
}

public static boolean groupSum(int[] arr, int target, int sum, int start) {
    if (sum > target) {
        return false;
    }
    // NOTE: sum == target inside of end of array check so all 5s are found.
    if (start >= arr.length) {
        return sum == target;
    }
    //choose
    sum = sum + arr[start];
    //explore
    if (groupSum(arr, target, sum, start + 1))
        return true;
    //un-choose
    // NOTE: can't unchoose 5
    if (5 == arr[start]) {
        return false;
    }
    sum = sum - arr[start];
    return groupSum(arr, target, sum, start + 1);
}

Обновление: Вот совет о том, как решать подобные проблемы.

  1. Очень четко укажите, что вы хотите, чтобы функция делала.
  2. Очень четко укажите, в каком базовом случае или случаях вы знаете ответ.
  3. В сложном случае выясните, как свести его к одной или нескольким более простым задачам.

Пока вы это делаете, ваш рекурсивный код должен работать.И если вы сомневаетесь в том, как вносить изменения, начните с нуля, только копируя код с того места, где вы заметили, что его можно оставить в покое.

Итак, для первого шага утверждение таково: Мы хотим, чтобы groupSum взял массив arr положительных целых чисел, цель target, частичную сумму sum и целое число start и возвратил, можно ли получить остаток массива вСумма к target, когда вы берете подмножество, которое должно включать все 5 с.

Для второго шага базовые случаи:

  • Мы уже превысили target, тогда это false.
  • Мы достигли конца массива и находимся в target, тогда это true.
  • Мы достигликонец массива и дует target, тогда это false.(Я совместил это с последним в коде, возвращая сравнение.)

Для третьего шага сокращения следующие:

  • Если мы можем добавитьтекущее значение и сделать его, ответ будет true.
  • Если текущее значение не 5, мы не добавляем его, и можем сделать его, ответ true.
  • В противном случае это неверно.

Я пытался написать код таким образом, который больше всего походил бы на то, что у вас уже было.Но написать это точно в соответствии с этой логикой было бы так: 

public static boolean groupSumWithAll5s(int[] arr, int target, int sum, int start) {
    // Base cases
    if (sum > target) {
        return false;
    }
    else if ((start >= arr.length) && (sum == target)) {
        return true;
    }
    else if (start >= arr.length) {
        return false;
    }

    // Recursive cases.
    if (groupSumWithAll5s(arr, target, sum + arr[start], start + 1)) {
        return true;
    }
    else if ((arr[start] != 5) && groupSumWithAll5s(arr, target, sum, start + 1)) {
        return true;
    }
    else {
        return false;
    }
}
...