Здравствуйте, 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); }
Попросили помочь с задачкой, и что-то она у меня не идет
Собственно все просто: необходимо рекурсивно реализовать решение задачи о рюкзаке (0/1). Не могу представить себе как выглядит перебор всех вариантов в рекурсии...
Здравствуйте, Chichikadze, Вы писали:
C>Попросили помочь с задачкой, и что-то она у меня не идет
C>Собственно все просто: необходимо рекурсивно реализовать решение задачи о рюкзаке (0/1). Не могу представить себе как выглядит перебор всех вариантов в рекурсии...
Пусть дан вектор размеров рюкзаков и вектор размеров предметов.
Требуется получить вектор, указывающий принадлежность каждого предмета тому или иному рюкзаку (т.е. элементы этого вектора — номера рюкзаков или 0, если соответствующий предмет никуда не положили).
Очевидно, рекурсивная функция делает следующее:
— берёт последний предмет и поочерёдно пытается пристроить его в рюкзаки
— в случае удачи, уменьшает ёмкость выбранного рюкзака и рекурсивно вызывает себя, передавая скорректированный вектор рюкзаков и укороченный вектор предметов
— если та функция возвращает признак неудачи, то переходим к следующему рюкзаку...
— если неудачно перебрали все рюкзаки — возвращаем признак неудачи
— а если вернули признак удачи и вектор размещений, то дописываем в него размещение нашего последнего предмета и возвращаем его с признаком удачи.
Дальнейшие уточнения алгоритма зависят от выбранного языка программирования.
На мутабельных векторах (С++, CaML) будет одно, на константных векторах (APL, J, K) — другое, на списках (Lisp, Haskell) — третье.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Chichikadze, Вы писали:
C>>Попросили помочь с задачкой, и что-то она у меня не идет
C>>Собственно все просто: необходимо рекурсивно реализовать решение задачи о рюкзаке (0/1). Не могу представить себе как выглядит перебор всех вариантов в рекурсии...
К>Дальнейшие уточнения алгоритма зависят от выбранного языка программирования. К>На мутабельных векторах (С++, CaML) будет одно, на константных векторах (APL, J, K) — другое, на списках (Lisp, Haskell) — третье.
Язык намного проще -- С.
Для меня сейчас вопрос не в этом. Как я понимаю, для поиска наилучшего варианта необходим полный перебор.
Перебор я представляю себе так (для пяти элментов):
1, 2, 3, 4, 5 (вдруг какая-то вещь, дороже всех остальных, даже если мы возьмем только ее)
И собственно это не могу уложить в рекурсию. Либо у меня не совсем корректое представление о переборе, либо одно из двух
Т.е. у нас есть группы, с увеличивающимся кол-вом членов. Когда в группе более одного члена надо последовательно передвигать элементы слева направо. При этом, самый правый элемент будет двигаться больше всех. Вроде так.
Осталось самое простое -- загнать это в рекурсию, что мне пока не удалось
Здравствуйте, Chichikadze, Вы писали:
К>>На мутабельных векторах (С++, CaML) будет одно, на константных векторах (APL, J, K) — другое, на списках (Lisp, Haskell) — третье. C>Язык намного проще -- С.
Что на Си, что на плюсах... Примерно одинаково. На плюсах можно повыделываться с итераторами.
А вообще, три глобальных массива (рюкзаки, предметы, индексы) и целое число (номер текущего элемента) в качестве параметра функции. Вот и все дела.
C>Для меня сейчас вопрос не в этом. Как я понимаю, для поиска наилучшего варианта необходим полный перебор.
C>Перебор я представляю себе так (для пяти элментов):
<> C>И собственно это не могу уложить в рекурсию. Либо у меня не совсем корректое представление о переборе, либо одно из двух
Как именно уложить это в рекурсию — я уже предложил выше. Возможно, сделал это невнятно.
Во-первых, о представлении групп. Ты предлагаешь каждому рюкзаку приписывать некоторое множество (номеров) предметов. Это возможно, но очень неэкономно. Гораздо проще приписать каждому предмету номер рюкзака, в который он будет положен — поскольку предмет нельзя положить сразу в несколько рюкзаков, то раскладке соответствует одномерный массив, а не двумерный массив с рваным краем или какие-то там списки.
Во-вторых, о переборе. Полный перебор — это... Поскольку каждый предмет независимо от других мы можем (попытаться) засунуть в каждый рюкзак поочерёдно либо отложить в сторону, то перебору соответствует N-разрядный (B+1)-ричный счётчик (где N — число предметов, B — число рюкзаков).
Разумеется, можно и нужно выполнять отсечку.
— Если первые k разрядов нашего счётчика дали переполнение какого-то рюкзака, то нет смысла щёлкать оставшиеся N-k разрядов: откатываемся к k-1'му.
— Можно следить за общим количеством свободного места в рюкзаках.
Здравствуйте, Chichikadze, Вы писали:
C>Пардон, был не внимателен -- рюкзак у нас всего один, к счастью
Ещё проще: значит, каждый предмет может быть либо положен, либо не положен в этот рюкзак. Двоичный вектор (а если количество предметов не больше разрядности целого числа (т.е. 32 или 64) — то вообще можно представить в виде целого числа и играть с битами).
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Chichikadze, Вы писали:
К>>>На мутабельных векторах (С++, CaML) будет одно, на константных векторах (APL, J, K) — другое, на списках (Lisp, Haskell) — третье. C>>Язык намного проще -- С.
К>Во-первых, о представлении групп. Ты предлагаешь каждому рюкзаку приписывать некоторое множество (номеров) предметов. Это возможно, но очень неэкономно. Гораздо проще приписать каждому предмету номер рюкзака, в который он будет положен — поскольку предмет нельзя положить сразу в несколько рюкзаков, то раскладке соответствует одномерный массив, а не двумерный массив с рваным краем или какие-то там списки.
К>Во-вторых, о переборе. Полный перебор — это... Поскольку каждый предмет независимо от других мы можем (попытаться) засунуть в каждый рюкзак поочерёдно либо отложить в сторону, то перебору соответствует N-разрядный (B+1)-ричный счётчик (где N — число предметов, B — число рюкзаков).
Пардон, не указал сразу, что рюкзак один...
К>Разумеется, можно и нужно выполнять отсечку. К>- Если первые k разрядов нашего счётчика дали переполнение какого-то рюкзака, то нет смысла щёлкать оставшиеся N-k разрядов: откатываемся к k-1'му.
Да, понятно, что если в рюкзак более ничего не лезет, то пытаться далее смысла нет и надо отходить на начальную позицию.
К>- Можно следить за общим количеством свободного места в рюкзаках.
К>Программа на Си очень простая получается . Удачи!
Это как раз таки и обидно вроде все просто, а столько бьюсь...
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Chichikadze, Вы писали:
К>>>Во-вторых, о переборе. Полный перебор — это... Поскольку каждый предмет независимо от других мы можем (попытаться) засунуть в каждый рюкзак поочерёдно либо отложить в сторону, то перебору соответствует N-разрядный (B+1)-ричный счётчик (где N — число предметов, B — число рюкзаков).
C>>Пардон, не указал сразу, что рюкзак один...
К>А это не имеет значения, сколько рюкзаков. Для одного рюкзака счётчик (двоичный) сделать легче.
К>>>Программа на Си очень простая получается . Удачи!
C>>Это как раз таки и обидно вроде все просто, а столько бьюсь...
К>Эх, ладно. Ответ.
Гммм... Пардон, сразу не дал полное условие задачи...
У каждой вещи есть цена и вес. Необходимо найти такую комбинацию, которая влезет в многострадальный рюкзак и стоимость положенных вещей будет максимальной. Поэтому я и думал о полном переборе...
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Chichikadze, Вы писали:
К>>>Во-вторых, о переборе. Полный перебор — это... Поскольку каждый предмет независимо от других мы можем (попытаться) засунуть в каждый рюкзак поочерёдно либо отложить в сторону, то перебору соответствует N-разрядный (B+1)-ричный счётчик (где N — число предметов, B — число рюкзаков).
C>>Пардон, не указал сразу, что рюкзак один...
К>А это не имеет значения, сколько рюкзаков. Для одного рюкзака счётчик (двоичный) сделать легче.
К>Эх, ладно. Ответ.
Огромное спасибо! Доработал напильником, теперь все работает как надо .
Здравствуйте, Chichikadze, Вы писали:
C>У каждой вещи есть цена и вес. Необходимо найти такую комбинацию, которая влезет в многострадальный рюкзак и стоимость положенных вещей будет максимальной. Поэтому я и думал о полном переборе...
Если ты изначально упорядочишь предметы в порядке убывания цены — то, перебирая от 111...1 к 000...0, получишь последовательность комбинаций, убывающую по цене. Соответственно, первая же встреченная комбинация, которая влезет в рюкзак, — и будет решением твоей задачи.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Chichikadze, Вы писали:
C>>У каждой вещи есть цена и вес. Необходимо найти такую комбинацию, которая влезет в многострадальный рюкзак и
К>Если ты изначально упорядочишь предметы в порядке убывания цены — то, перебирая от 111...1 к 000...0, получишь
Если бы... По условию задачи мне нужна была именно рекурсия .
Здравствуйте, Chichikadze, Вы писали:
К>>Если ты изначально упорядочишь предметы в порядке убывания цены — то, перебирая от 111...1 к 000...0, получишь
C>Если бы... По условию задачи мне нужна была именно рекурсия .
Ой, как будто это проблема — ввести рекурсию!
Пусть за каждый разряд отвечает свой уровень рекурсии. Грубо говоря,
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Chichikadze, Вы писали:
К>>>Если ты изначально упорядочишь предметы в порядке убывания цены — то, перебирая от 111...1 к 000...0, получишь
C>>Если бы... По условию задачи мне нужна была именно рекурсия .
К>Ой, как будто это проблема — ввести рекурсию!
Работу уже сдал, сказали, что вроде все в порядке.
Но, как я понимаю, при условии сохранения рекурсии поиск (без сортировки) все равно будет быстрее -- не надо передвигать элементы. Правда, искать надо всегда сначала, а работать можно с единожды отсортированным.
И еще: если я правильно тебя понял, то может случиться ситуация:
W: 6 5 5
V: 7 4 4
MaxW: 10.
Тогда, если мы берем только первый элемент (2ой уже не влезет) то проиграем. При таком максимальном весе лучше взять 2 последних -- при них выигрышь будет больше.
Здравствуйте, Chichikadze, Вы писали:
C>Но, как я понимаю, при условии сохранения рекурсии поиск (без сортировки) все равно будет быстрее -- не надо передвигать элементы. Правда, искать надо всегда сначала, а работать можно с единожды отсортированным.
Естественно: один раз отсортировали, и понеслась!
C>И еще: если я правильно тебя понял, то может случиться ситуация: