VPF::полный перебор с рекурсией - Форум программистов

Pawl

Дата 10.1.2012, 14:24 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: нет
Всего: 28

Доброго времени суток!
Плохо умею составлять алгоритмы с древовидной рекурсией (меня хватает только на числа фибоначчи и похожие простые задачи). А тут понадобилось реализовать полный перебор с древовидной рекурсией, и я прошу Вашей помощи. Задача такая: в числовом массиве найти все комбинации чисел, составляющих данную сумму. Такой перебор можно организовать с помощью вложенных циклов, но когда я пытаюсь организовать его рекурсивно, получается полная хрень. Вот мой код (привожу его на java). Если он вызовет у Вас удивление, недоумение, возмущение, гнев или другие сильные чувства, пожалуйста, не поддавайтесь им, а спокойно вдохните и на выдохе медленно досчитайте до 10. Если с 1-го раза не поможет, процедуру повторите smile

Код


import java.util.*;

public class Summ1 {
    // заданный массив
    static final int NUM[] = {11, 2, 30, 19, 44, 15, 10, 15, 20, 30};
    // его длина
    static final int COUNT = NUM.length;
    // заданная сумма
    static final int SUM = 30;    
    // список для хранения одной комбинации чисел, составляющих заданную сумму
    static LinkedList<Integer> sum = new LinkedList<Integer>();
    // список для хранения всех комбинаций чисел, составляющих заданную сумму
    static LinkedList<LinkedList<Integer>> sumList = new LinkedList<LinkedList<Integer>>();
    // переменная, хранящая значение текущей суммы
    static int s;
    
    // ss - значение суммы на предыдущем шаге рекурсии
    public static void find(int ss, int i) {
      // если текущая сумма равна заданной, сохраняем комбинацию чисел, которые составляют текущую сумму
          if (s == SUM) {
              sumList.add(new LinkedList<Integer>(sum));
              // очищаем список чисел
              sum.clear();
          }
      
        for (int j = 0; j < COUNT; j++) {
            // проверка j не равно i организована, чтобы не суммировать числа сами с собой
            if (j != i) {            
                s = ss + NUM[j];
                /* 
                 * если текущая сумма не больше SUM, в список чисел добавляется j-й элемент
                 * и вызываем рекурсию с новым значением суммы
                 */                                                                                
                if (s <= SUM) {                     
                    sum.add(NUM[j]);                    
                    find(s, j);                    
                }
            }                                                                                        
        }                    
    }
    
    public static void main(String[] args) {
     find(0, -1);
     // вывод всех комбинаций чисел, составляющих данную сумму
     for (LinkedList<Integer> sl : sumList) {
         System.out.println(sl);
     }              
    }
}

Спасбо заранее за помощь в исправлении моих ошибок и, в особенности, за доступное описание того, что и почему надо исправить!

--------------------

В действительности всё совсем не так, как на самом деле

Lipetsk

Дата 11.1.2012, 08:01 (ссылка)

(нет голосов)

Загрузка ...

в форме ;)

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 28.1.2009
Где: Липецк

Репутация: 2
Всего: 5

дело в том, что нужно помечать все использованные числа, чтобы не использовать их повторно
а вы сейчас "помечаете" только последнее использованное число

Pawl

Дата 11.1.2012, 10:50 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: нет
Всего: 28

Цитата(Lipetsk @ 11.1.2012, 08:01

)

дело в том, что нужно помечать все использованные числа, чтобы не использовать их повторно

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

--------------------

В действительности всё совсем не так, как на самом деле

Pawl

Дата 19.1.2012, 13:12 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: нет
Всего: 28

Сделал программу на основе алгоритма перестановок элементов в массиве:

Код


import java.util.*;

public class PerestInt {
    private static final int SUM = 10;
    private static final int[] a = {2, 5, 3, 1, 4, 10};
    private static final int m = a.length;
    private static int[] pole = new int[m];    
    private static ArrayList<ArrayList<Integer>> summs = new ArrayList<ArrayList<Integer>>();
    
    public static void perest(int n, int[] r) {
        int[] r1 = new int[m];        
        if (n == m) {
            sum(pole);                
        } else {
            for (int i = 0; i < m - n; i++) {
                pole[n] = r[i];
                int k = 0;            
                for (int j = 0; j < m - n; j++) {
                    if (j != i) {
                        r1[k] = r[j];
                        k++;
                    }
                }
                perest(n + 1, r1);
            }
        }
    }
    
    private static void sum(int [] p) {
        ArrayList<Integer> v = new ArrayList<Integer>();            
        int s = 0;
        for(int el : p) {
            s += el;
            if (s <= SUM) {
                v.add(el);
                Collections.sort(v);
            }
            
            if (s == SUM && !summs.contains(v)) {                
                summs.add(v);
                break;
            }
        }
    }
        
    public static void main(String[] args) {
        perest(0, a);
        for(ArrayList<Integer> v : summs) {
            System.out.println(v);
        }
    }
}

Однако, как видно, она совсем не оптимально работает: подсчет суммы производится абсолютно для всех вариантов, а хотелось бы, чтобы он не производился, к примеру, для повторяющихся вариантов, а также тогда, когда сумма элементов начинает превышать заданную.
Был бы очень благодарен за помощь в оптимизации моего кода!

--------------------

В действительности всё совсем не так, как на самом деле

Pawl

Дата 22.1.2012, 01:04 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: нет
Всего: 28

В общем, сделал я, что хотел, применив для этого метод ветвей и границ (или перебор с отсечением? - Поправьте меня, если что smile

). Вот код:

Код


import java.util.*;

public class PerestInt {
    private static final int SUM = 10;
    private static final int[] a = {2, 5, 3, 1, 5, 4, 20, 7, 10};
    private static final int m = a.length;
    private static int[] pole = new int[m];    
    private static ArrayList<ArrayList<Integer>> summs = new ArrayList<ArrayList<Integer>>();
    private static int s = 0;
    private static ArrayList<Integer> v = new ArrayList<Integer>();
    
    public static void perest(int n, int[] r) {        
        int[] r1 = new int[m];        
        if (s == SUM) {
            sum();                
        }
        
        for (int i = 0; i < m - n; i++) {
            pole[n] = r[i];            
            if (s < SUM && !v.contains(pole[i])) {
                s += pole[n];
                v.add(pole[n]);
                Collections.sort(v);
                
                int k = 0;            
                for (int j = 0; j < m - n; j++) {
                    if (j != i) {
                        r1[k] = r[j];
                        k++;
                    }
                }
                perest(n + 1, r1);
                s = 0;
                v.clear();
            }
        }
    }
    
    private static void sum() {            
        if (!summs.contains(v)) {                
            summs.add(new ArrayList<Integer>(v));
            v.clear();
        }
    }
        
    public static void main(String[] args) {
        perest(0, a);
        for(ArrayList<Integer> v : summs) {
            System.out.println(v);
        }
    }
}

Код, конечно, сыроват, но, если кому надо - пишите. Я все-равно буду его "причесывать", делать комменты и пр. В принципе, могу выложить и в товарном виде - мне не жалко! smile

З. Ы. А плодотворный у нас с вами все-же диалог получился, товарисчи! smile

З. З. Ы. Знаете, когда собирал в нете инфу по задаче, на форумах видел много просьб помочь ее решить, и везде сталкивался с сакраментальной фразой, типа, она решается просто методом тупого перебора. Но самого переборного решения никто нигде не приводил. Может, потому, что этот перебор таки не так прост и туп?

Добавлено через 1 минуту и 25 секунд
Тема закрыта

--------------------

В действительности всё совсем не так, как на самом деле

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »