|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
11.01.2011, 21:33 | #1 |
Форумчанин
Регистрация: 24.03.2009
Сообщений: 375
|
Задача о рюкзаке
Объясните, пожалуйста, на словах, алгоритм решения Задачи о рюкзаке.
|
11.01.2011, 22:19 | #2 |
Форумчанин
Регистрация: 02.07.2010
Сообщений: 167
|
Если я не ошибаюсь следует создать полный перебор вориантов и по ходу проверки кождого варианта на условие непереполнение стоимости и веса, выискивать оптимальный вариант.
Если я тебе помог, помоги и ты мне +ом с комментарием
|
11.01.2011, 22:27 | #3 |
Пользователь
Регистрация: 03.01.2011
Сообщений: 80
|
Итак, пусть у нас есть рюкзак объёма W, и список из n вещей, у каждой из которых есть объём v[i] и стоимость c[i], и каждую из которых можно брать сколько угодно раз. При этом все объёмы и все стоимости будут положительными и целыми. Как же работает алгоритм?
Заведём массив max длины W+1, в котором мы по итогам работы алгоритма получим наибольшую стоимость, которую может иметь набор вещей, занимающий данный объём — для каждого объёма от 0 до W включительно. А точнее, после k итераций мы получим для каждого объёма i max[i] — максимальную возможную стоимость набора вещей объёма i, в котором могут быть только первые k вещей. Сразу понятно, что изначально надо инициализировать max[0] = 0. Что же остальные элементы max? Не используя никаких вещей, можно получить только набор веса 0. Значит, в max[i] (0 < i <= W) нужно записать что-то, что будет хуже, чем любая возможная стоимость набора веса i. Например, -1. После этого надо сделать n итераций. На k-той итерации мы делаем следующее. До итерации в массиве в каждом элементе max[i] записана максимальная возможная стоимость набора вещей веса i, который составлен из вещей 0..k-1. Каждый раз, рассматривая элемент max[i], мы добьёмся того, чтобы там была записана максимальная возможная стоимость набора вещей веса i, который составлен из вещей 0..k. Для этого проверим, в оптимальном наборе вообще есть k-тая вещь, хотя бы одна? Если нет, то в max[i] уже записана оптимальная стоимость. Если есть, то, если из этого набора выкинуть одну k-тую вещь, то получится оптимальный набор вещей объёма i-v[k], оставленный из вещей 0..k. Но последний уже записан в max[i-v[k]]! Значит, надо просто сравнить величины max[i] и max[i-v[k]] + c[k] (если, конечно, i >= v[k]). Максимальную из них и надо записать в max[i]. Итак, после k-той итерации мы полчим в каждом max[i] наибольшую стоимость, которую может имет набор вещей, составленный из вещей. Значит, после n итераций мы получим именно то, что и обещалось. Осталось дело техники: пройтись по массиву max[i] и выбрать в нём максимальный элемент. Как несложно заметить, ассимптотика времени работы алгоритма будет O(W*n), и используемой памяти — O(W). Вариации: 1. Когда надо получить не только стоимость, но и сам набор. Кроме массива max, запишем ещё и массив prev. В него мы будем записывать, какую вещь мы последний раз положили в набор. То есть, если при сравнении max[i] и max[i-v[k]] + c[k] оказалось, что max[i-v[k]] + c[k] лучше — это означает, что в оптимальном наборе веса i должен быть k-тый предмет. Таким образом, если мы выяснили, что оптимальная стоимость max[i] достигается при наборе веса i, то можно записать, что мы добавили в набор вещь prev[i]. И перейти к оптимальному набору веса i — v[prev[i]]. Там тоже посмотреть, какую вещь взяли в последний раз. И так далее, пока не дойдём до нуля. 2. Когда каждую вещь можно брать только один раз. Тут всё ещё проще: надо просто в каждй итерации идти по массиву не снизу вверх, а сверху вниз, то есть, от W к 0. Тогда получится, что при рассмотрении max[i-v[k]], там всё ещё будет записано, набор какой максималльной стоимости веса i — v[k] можно получить, используя только вещи 0..k-1. Следовательно, если получится, что в оптимальном наборе надо использовать k-тую вещь, то она будет использована только один раз. 3. Выбор значения, как можно более близкого к данному. Если нет стоимостей, то данный алгоритм, очевидно, помогает как можно сильнее набить рюкзак. Или же, если речь идёт не о рюкзаке, и неважно, что общий объём вещей не больше объёма рюкзака, можно из нескольких чисел с помощью сложения получить число, как можно более близкое к данному. В всех случаях ассимптотика времени работы и используемой памяти та же. 4. Когда каждую вещь можно брать определённое количество раз. За эту вариацию спасибо lipstick. Есть вариация задачи, в которой вещь с номером i можно брать от 0 до q[i] раз. Конечно, можно «размножить» i-ю вещь на q[i] единиц и решить задачу о 0-1 рюкзаке. Однако, сложность такого решения будет O(W * ∑q[i]), что не очень хорошо. На самом деле, можно поступить хитрее. Пусть q[i] = 1 + 2 + 4 + 8 +… + 2^k + r[i], где r[i] < 2^(k+1). Тогда рассмотрим k+2 предмета объёмом 1*v[i], 2*v[i], ..., 2^k*v[i], r[i]*v[i] и стоимостью 1*c[i], 2*c[i], ..., 2^k*c[i], r[i]*c[i] соответственно. («Названия» новых предметов — «1 i-я вещь», «2 i-ых вещи», «4 i-ых вещи» и т. д.) Ясно, что выбирая различные подмножества этих k+2 предметов, можно получить любое количество (от 0 до q[i]) вещей типа i. Т. е. вместо «размножения» вещей i-го типа на q[i] единиц, мы сумели ограничиться k+2 = O(log q[i]) единицами. Такой метод будет иметь сложность порядка O(W * ∑log q[i]), что куда более эффективно, чем «наивное» решение.
Хорошо, Java, ВОЗМОЖНО, хороший пример того как должен выглядеть язык. Но тогда программы на Java — это хороший пример как НЕЛЬЗЯ писать программы
|
11.01.2011, 22:28 | #4 |
Пользователь
Регистрация: 03.01.2011
Сообщений: 80
|
Google рулит)
Хорошо, Java, ВОЗМОЖНО, хороший пример того как должен выглядеть язык. Но тогда программы на Java — это хороший пример как НЕЛЬЗЯ писать программы
|
12.01.2011, 00:11 | #5 |
Форумчанин
Регистрация: 21.10.2010
Сообщений: 130
|
Sabin4ik, этот алгоритм только для целочисленных весов и стоимостей.
|
16.09.2011, 20:07 | #6 |
Пользователь
Регистрация: 17.02.2010
Сообщений: 13
|
привет.а не подскажете решение этой же задачи когда только одно ограничение - объем загружаемыых предметов - с или d.и брать можно только один раз.
только не на словах))) язык - QBasic |
16.09.2011, 20:44 | #7 |
Форумчанин
Регистрация: 29.05.2011
Сообщений: 449
|
excel поиск решений и вообще нет проблем
задания на pascal/delphi ICQ 368254335
Tel +79177425326 mail denis-naymov1985(at)mail.ru login skype denis.new.skype |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задача на С++ | Перфаратар | Помощь студентам | 1 | 21.10.2010 23:09 |
Задача | Виталя5230 | Помощь студентам | 4 | 20.10.2010 16:57 |
Ручной режим Задачи о Рюкзаке в Delphi | oblachko | Помощь студентам | 1 | 07.06.2009 23:26 |