Рюкзак, рекурсия, классика...
От: Chichikadze Израиль http://mika0x65.livejournal.com
Дата: 07.01.06 00:14
Оценка:
Мое почтение всем.

Попросили помочь с задачкой, и что-то она у меня не идет

Собственно все просто: необходимо рекурсивно реализовать решение задачи о рюкзаке (0/1). Не могу представить себе как выглядит перебор всех вариантов в рекурсии...

Стыдно, но need help!..
Re: Рюкзак, рекурсия, классика...
От: Кодт Россия  
Дата: 07.01.06 15:15
Оценка:
Здравствуйте, Chichikadze, Вы писали:

C>Попросили помочь с задачкой, и что-то она у меня не идет


C>Собственно все просто: необходимо рекурсивно реализовать решение задачи о рюкзаке (0/1). Не могу представить себе как выглядит перебор всех вариантов в рекурсии...


Пусть дан вектор размеров рюкзаков и вектор размеров предметов.
Требуется получить вектор, указывающий принадлежность каждого предмета тому или иному рюкзаку (т.е. элементы этого вектора — номера рюкзаков или 0, если соответствующий предмет никуда не положили).

Очевидно, рекурсивная функция делает следующее:
— берёт последний предмет и поочерёдно пытается пристроить его в рюкзаки
— в случае удачи, уменьшает ёмкость выбранного рюкзака и рекурсивно вызывает себя, передавая скорректированный вектор рюкзаков и укороченный вектор предметов
— если та функция возвращает признак неудачи, то переходим к следующему рюкзаку...
— если неудачно перебрали все рюкзаки — возвращаем признак неудачи
— а если вернули признак удачи и вектор размещений, то дописываем в него размещение нашего последнего предмета и возвращаем его с признаком удачи.

Дальнейшие уточнения алгоритма зависят от выбранного языка программирования.
На мутабельных векторах (С++, CaML) будет одно, на константных векторах (APL, J, K) — другое, на списках (Lisp, Haskell) — третье.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[2]: Рюкзак, рекурсия, классика...
От: Chichikadze Израиль http://mika0x65.livejournal.com
Дата: 07.01.06 16:36
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Chichikadze, Вы писали:


C>>Попросили помочь с задачкой, и что-то она у меня не идет


C>>Собственно все просто: необходимо рекурсивно реализовать решение задачи о рюкзаке (0/1). Не могу представить себе как выглядит перебор всех вариантов в рекурсии...


К>Дальнейшие уточнения алгоритма зависят от выбранного языка программирования.

К>На мутабельных векторах (С++, CaML) будет одно, на константных векторах (APL, J, K) — другое, на списках (Lisp, Haskell) — третье.

Язык намного проще -- С.

Для меня сейчас вопрос не в этом. Как я понимаю, для поиска наилучшего варианта необходим полный перебор.

Перебор я представляю себе так (для пяти элментов):

1, 2, 3, 4, 5 (вдруг какая-то вещь, дороже всех остальных, даже если мы возьмем только ее)

далее:

1-2, 1-3, 1-4, 1-5.
2-3, 2-4, 2-5.
3-4, 3-5.
4-5.

1-2-3, 1-2-4, 1-2-5.
1-3-4, 1-3-5.
1-4-5.

2-3-4, 2-3-5.
2-4-5.

1-2-3-4, 1-2-3-5.
1-3-4-5.

2-3-4-5.

1-2-3-4-5.

И собственно это не могу уложить в рекурсию. Либо у меня не совсем корректое представление о переборе, либо одно из двух

Т.е. у нас есть группы, с увеличивающимся кол-вом членов. Когда в группе более одного члена надо последовательно передвигать элементы слева направо. При этом, самый правый элемент будет двигаться больше всех. Вроде так.

Осталось самое простое -- загнать это в рекурсию, что мне пока не удалось
Re[3]: Рюкзак, рекурсия, классика...
От: Chichikadze Израиль http://mika0x65.livejournal.com
Дата: 07.01.06 16:38
Оценка:
Здравствуйте, Chichikadze, Вы писали:

C>Здравствуйте, Кодт, Вы писали:


Пардон, был не внимателен -- рюкзак у нас всего один, к счастью
Re[3]: Рюкзак, рекурсия, классика...
От: Кодт Россия  
Дата: 07.01.06 17:06
Оценка:
Здравствуйте, Chichikadze, Вы писали:

К>>На мутабельных векторах (С++, CaML) будет одно, на константных векторах (APL, J, K) — другое, на списках (Lisp, Haskell) — третье.

C>Язык намного проще -- С.

Что на Си, что на плюсах... Примерно одинаково. На плюсах можно повыделываться с итераторами.
А вообще, три глобальных массива (рюкзаки, предметы, индексы) и целое число (номер текущего элемента) в качестве параметра функции. Вот и все дела.

C>Для меня сейчас вопрос не в этом. Как я понимаю, для поиска наилучшего варианта необходим полный перебор.


C>Перебор я представляю себе так (для пяти элментов):

<>
C>И собственно это не могу уложить в рекурсию. Либо у меня не совсем корректое представление о переборе, либо одно из двух

Как именно уложить это в рекурсию — я уже предложил выше. Возможно, сделал это невнятно.

Во-первых, о представлении групп. Ты предлагаешь каждому рюкзаку приписывать некоторое множество (номеров) предметов. Это возможно, но очень неэкономно. Гораздо проще приписать каждому предмету номер рюкзака, в который он будет положен — поскольку предмет нельзя положить сразу в несколько рюкзаков, то раскладке соответствует одномерный массив, а не двумерный массив с рваным краем или какие-то там списки.

Во-вторых, о переборе. Полный перебор — это... Поскольку каждый предмет независимо от других мы можем (попытаться) засунуть в каждый рюкзак поочерёдно либо отложить в сторону, то перебору соответствует N-разрядный (B+1)-ричный счётчик (где N — число предметов, B — число рюкзаков).

Разумеется, можно и нужно выполнять отсечку.
— Если первые k разрядов нашего счётчика дали переполнение какого-то рюкзака, то нет смысла щёлкать оставшиеся N-k разрядов: откатываемся к k-1'му.
— Можно следить за общим количеством свободного места в рюкзаках.

Программа на Си очень простая получается . Удачи!
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[4]: Рюкзак, рекурсия, классика...
От: Кодт Россия  
Дата: 07.01.06 17:09
Оценка:
Здравствуйте, Chichikadze, Вы писали:

C>Пардон, был не внимателен -- рюкзак у нас всего один, к счастью


Ещё проще: значит, каждый предмет может быть либо положен, либо не положен в этот рюкзак. Двоичный вектор (а если количество предметов не больше разрядности целого числа (т.е. 32 или 64) — то вообще можно представить в виде целого числа и играть с битами).
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[4]: Рюкзак, рекурсия, классика...
От: Chichikadze Израиль http://mika0x65.livejournal.com
Дата: 07.01.06 17:17
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Chichikadze, Вы писали:


К>>>На мутабельных векторах (С++, CaML) будет одно, на константных векторах (APL, J, K) — другое, на списках (Lisp, Haskell) — третье.

C>>Язык намного проще -- С.

К>Во-первых, о представлении групп. Ты предлагаешь каждому рюкзаку приписывать некоторое множество (номеров) предметов. Это возможно, но очень неэкономно. Гораздо проще приписать каждому предмету номер рюкзака, в который он будет положен — поскольку предмет нельзя положить сразу в несколько рюкзаков, то раскладке соответствует одномерный массив, а не двумерный массив с рваным краем или какие-то там списки.


К>Во-вторых, о переборе. Полный перебор — это... Поскольку каждый предмет независимо от других мы можем (попытаться) засунуть в каждый рюкзак поочерёдно либо отложить в сторону, то перебору соответствует N-разрядный (B+1)-ричный счётчик (где N — число предметов, B — число рюкзаков).


Пардон, не указал сразу, что рюкзак один...

К>Разумеется, можно и нужно выполнять отсечку.

К>- Если первые k разрядов нашего счётчика дали переполнение какого-то рюкзака, то нет смысла щёлкать оставшиеся N-k разрядов: откатываемся к k-1'му.

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

К>- Можно следить за общим количеством свободного места в рюкзаках.


К>Программа на Си очень простая получается . Удачи!


Это как раз таки и обидно вроде все просто, а столько бьюсь...

Спасибо
Re[5]: Рюкзак, рекурсия, классика...
От: Кодт Россия  
Дата: 07.01.06 18:00
Оценка: 4 (1)
Здравствуйте, Chichikadze, Вы писали:

К>>Во-вторых, о переборе. Полный перебор — это... Поскольку каждый предмет независимо от других мы можем (попытаться) засунуть в каждый рюкзак поочерёдно либо отложить в сторону, то перебору соответствует N-разрядный (B+1)-ричный счётчик (где N — число предметов, B — число рюкзаков).


C>Пардон, не указал сразу, что рюкзак один...


А это не имеет значения, сколько рюкзаков. Для одного рюкзака счётчик (двоичный) сделать легче.

К>>Программа на Си очень простая получается . Удачи!


C>Это как раз таки и обидно вроде все просто, а столько бьюсь...


Эх, ладно. Ответ.
int bag; // свободное место в рюкзаке
int items[N]; // размеры элементов
bool place[N]; // входит ли i-й элемент в рюкзак?

bool solve(int i) // i - текущий элемент
{
  if(bag == 0) return true; // кончилось место? значит, решение найдено
  if(i==N) return false; // кончились элементы, а рюкзак не упакован? значит, решение не найдено

  // вариант №1: положить текущий элемент (если влезает, конечно)
  if(items[i] < bag)
  {
    place[i] = true;
    bag -= items[i];
    if(solve(i+1)) return true;
    // неудача? восстановим статус-кво
    bag += items[i];
  }

  // №2: отложить в сторону
  place[i] = false;
  return solve(i+1); // поскольку это последний вариант, сразу и выйдем.
}

bool solve_now() { return solve(0); }
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[6]: Рюкзак, рекурсия, классика...
От: Chichikadze Израиль http://mika0x65.livejournal.com
Дата: 07.01.06 18:10
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Chichikadze, Вы писали:


К>>>Во-вторых, о переборе. Полный перебор — это... Поскольку каждый предмет независимо от других мы можем (попытаться) засунуть в каждый рюкзак поочерёдно либо отложить в сторону, то перебору соответствует N-разрядный (B+1)-ричный счётчик (где N — число предметов, B — число рюкзаков).


C>>Пардон, не указал сразу, что рюкзак один...


К>А это не имеет значения, сколько рюкзаков. Для одного рюкзака счётчик (двоичный) сделать легче.


К>>>Программа на Си очень простая получается . Удачи!


C>>Это как раз таки и обидно вроде все просто, а столько бьюсь...


К>Эх, ладно. Ответ.


Гммм... Пардон, сразу не дал полное условие задачи...

У каждой вещи есть цена и вес. Необходимо найти такую комбинацию, которая влезет в многострадальный рюкзак и стоимость положенных вещей будет максимальной. Поэтому я и думал о полном переборе...
Re[6]: Рюкзак, рекурсия, классика...
От: Chichikadze Израиль http://mika0x65.livejournal.com
Дата: 08.01.06 19:01
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Chichikadze, Вы писали:


К>>>Во-вторых, о переборе. Полный перебор — это... Поскольку каждый предмет независимо от других мы можем (попытаться) засунуть в каждый рюкзак поочерёдно либо отложить в сторону, то перебору соответствует N-разрядный (B+1)-ричный счётчик (где N — число предметов, B — число рюкзаков).


C>>Пардон, не указал сразу, что рюкзак один...


К>А это не имеет значения, сколько рюкзаков. Для одного рюкзака счётчик (двоичный) сделать легче.


К>Эх, ладно. Ответ.


Огромное спасибо! Доработал напильником, теперь все работает как надо .
Re[7]: Рюкзак, рекурсия, классика...
От: Кодт Россия  
Дата: 09.01.06 10:06
Оценка:
Здравствуйте, Chichikadze, Вы писали:

C>У каждой вещи есть цена и вес. Необходимо найти такую комбинацию, которая влезет в многострадальный рюкзак и стоимость положенных вещей будет максимальной. Поэтому я и думал о полном переборе...


Если ты изначально упорядочишь предметы в порядке убывания цены — то, перебирая от 111...1 к 000...0, получишь последовательность комбинаций, убывающую по цене. Соответственно, первая же встреченная комбинация, которая влезет в рюкзак, — и будет решением твоей задачи.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[8]: Рюкзак, рекурсия, классика...
От: Chichikadze Израиль http://mika0x65.livejournal.com
Дата: 09.01.06 11:30
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Chichikadze, Вы писали:


C>>У каждой вещи есть цена и вес. Необходимо найти такую комбинацию, которая влезет в многострадальный рюкзак и


К>Если ты изначально упорядочишь предметы в порядке убывания цены — то, перебирая от 111...1 к 000...0, получишь


Если бы... По условию задачи мне нужна была именно рекурсия .
Re[9]: Рюкзак, рекурсия, классика...
От: Кодт Россия  
Дата: 09.01.06 13:04
Оценка:
Здравствуйте, Chichikadze, Вы писали:

К>>Если ты изначально упорядочишь предметы в порядке убывания цены — то, перебирая от 111...1 к 000...0, получишь


C>Если бы... По условию задачи мне нужна была именно рекурсия .


Ой, как будто это проблема — ввести рекурсию!
Пусть за каждый разряд отвечает свой уровень рекурсии. Грубо говоря,
perform(s) =
  perform(s+"1"),
  perform(s+"0");
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[10]: Рюкзак, рекурсия, классика...
От: Chichikadze Израиль http://mika0x65.livejournal.com
Дата: 09.01.06 17:15
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Chichikadze, Вы писали:


К>>>Если ты изначально упорядочишь предметы в порядке убывания цены — то, перебирая от 111...1 к 000...0, получишь


C>>Если бы... По условию задачи мне нужна была именно рекурсия .


К>Ой, как будто это проблема — ввести рекурсию!


Работу уже сдал, сказали, что вроде все в порядке.

Но, как я понимаю, при условии сохранения рекурсии поиск (без сортировки) все равно будет быстрее -- не надо передвигать элементы. Правда, искать надо всегда сначала, а работать можно с единожды отсортированным.

И еще: если я правильно тебя понял, то может случиться ситуация:

W: 6 5 5
V: 7 4 4

MaxW: 10.

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

Или что-то не так понял?..
Re[11]: Рюкзак, рекурсия, классика...
От: Кодт Россия  
Дата: 09.01.06 17:50
Оценка:
Здравствуйте, Chichikadze, Вы писали:

C>Но, как я понимаю, при условии сохранения рекурсии поиск (без сортировки) все равно будет быстрее -- не надо передвигать элементы. Правда, искать надо всегда сначала, а работать можно с единожды отсортированным.


Естественно: один раз отсортировали, и понеслась!

C>И еще: если я правильно тебя понял, то может случиться ситуация:


Да, может тут я облажался.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.