|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
28.04.2010, 12:28 | #2 |
Пользователь
Регистрация: 30.03.2009
Сообщений: 23
|
Эмм по ссылке всё написано и даже довольно подробно описано, так-что нет смысла в copy-paste, а тема вообще не соответствует содержанию.
P.S. Пример вообще из Access... |
28.04.2010, 12:30 | #3 |
Форумчанин
Регистрация: 14.12.2009
Сообщений: 716
|
В универе попалась такая же задачка, только вычисление идут без всяких формул.
Решал методом Greedy, не знаю существует вообще такое понятие о таком методе, либо просто наш профессор дал имя этому методу. Суть метода в том, как можно выгодней положить предмет, чтобы в рюкзаке осталось больше места. Рюкзак Объект Пустое место Код:
|
28.04.2010, 14:12 | #4 | |
Новичок
Джуниор
Регистрация: 28.04.2010
Сообщений: 6
|
animalshadow, я понимаю полностью в чём заключается задача. Об этом подробно написано в Википедии, куда я дал ссылку. Почему я так назвал тему? Название такое потому, что я не понимаю формулу в общем виде. А C++ я не знаю и хотел, чтобы мне пояснили по шагам как алгоритм работает.
coNsept, про метод Greedy ничего не знаю, а по коду что он делает тоже понять не могу. Если бы Вы пояснили, то было бы очень хорошо. В моём примере (ссылка в первом сообщении) я всё делал без какого-либо математического алгоритма, заполнял решая всё в голове перебором. Имеются предметы номера i с весом w и стоимостью c: i w c 1 1 10 2 2 5 3 3 3 4 4 20 5 5 7 Заполнить рюкзак, который может выдержать вес w=10 предметами так, чтобы их стоимость была максимально возможной. Каждый предмет имеется только в единственном экземпляре. Решать перебором, как я это делал в голове нельзя, так как в настоящем примере будет очень много предметов, что будет занимать много времени. В моём примере я заполнял сначала рюкзак с весом w=1 предметом который который должен был при весе w=1 иметь максимальную стоимость (это ячейка B11). Затем я заполнял рюкзак с весом w=2 (ячейка B12), и так далее до веса рюкзака w=10 (до B20). Далее я уже выбирал из двух предметов, заполняя столбец C10:C20. И так далее по столбцам. Я не могу правильно понять формулу. Я понимаю так, что следующий максимальный элемент (жёлтый E15 в таблице) равен предыдущему (фиолетовый E14) + элемент с координатами строки "вес рюкзака, для которого мы считаем (w=5) - вес рюкзака на предыдущем шаге (w=4) = 1 (строка для веса рюкзака w=1)" и столбца "столбец элемента, для которого мы считаем (i=4) - 1 = 3 (столбец для трёх элементов i=3)" фиолетовый D11. Мне кажется, что я не так понял формулу, поэтому и прошу описать мне последовательность выполнения кода. Или же, кто понимает как эта формула работает, описать последовательность действий. Нашёл ещё видео, на котором это объясняют, но я что-то не пойму: Цитата:
Последний раз редактировалось fkorto; 28.04.2010 в 17:38. |
|
28.04.2010, 16:50 | #5 |
Форумчанин
Регистрация: 25.04.2010
Сообщений: 254
|
А в каком виде должно быть решение? Программа, язык, на листе Excel?
Порядок решения (для уменьшения вариантов перебора) следующий: рассчитать для каждого предмета дополнительный параметр (удельная стоимость = с/w) и отсортировать массив предметов по этому параметру по убыванию. До тех пор пока самые выгодные предметы умещаются в рукзак, туда им и дорога. Ну а потом, можно поварьировать последними (как правило максимум получается при полной загрузке всего рюкзака, но может быть и исключение).
помогать студентам - моя вторая профессия
|
28.04.2010, 17:19 | #6 |
Новичок
Джуниор
Регистрация: 28.04.2010
Сообщений: 6
|
was3110, решение особой роли не играет, так как мне нужно разобраться с формулой, на которую я дал ссылку. Я делаю в Excel, так как там мне проще. C++ я не знаю. Но мне подойдёт и Delphi. Решение в C++ есть (я дал ссылку сверху), но мне бы его кто-нибудь пояснил.
Про удельную стоимость я знаю, но она помогает при полном переборе, чтобы исключить полный перебор (я думаю смысл понятен). А у меня попытка уменьшения числа итераций с использованием формулы, про которую я и спрашиваю. |
29.04.2010, 15:12 | #7 |
Форумчанин
Регистрация: 25.04.2010
Сообщений: 254
|
Алгоритм из Википедии переписал на VBA. Массив просматривается в EXCEL. Для тестирования (изменения входных данных) должны быть включены макросы. Качай с сайта (мелкие задачки на VB и VBA). Контакты там же.
помогать студентам - моя вторая профессия
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Русский язык | Sanek_ntsk | Общие вопросы C/C++ | 9 | 06.03.2008 16:50 |
Русский язык | Elefanter | Свободное общение | 14 | 22.02.2008 16:23 |
Русский язык | [Smarik] | Паскаль, Turbo Pascal, PascalABC.NET | 7 | 01.02.2008 22:58 |
РУССКИЙ ЯЗЫК | vicdon | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 19.11.2007 14:34 |
переход на русский язык | vicdon | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 05.11.2007 18:42 |