Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 75
интересный алгоритм, нужно будет посидеть разобраться
Вы исходите из ложной предпосылки о том, что всех можно разделить строго на две категории.
А я исхожу из комментариев к посту, ссылка на который содержится в теле этого поста.
А я исхожу из комментариев к посту, ссылка на который содержится в теле этого поста.
Да, но и не только. Я предполагаю, что есть люди, которым алгоритмы интересны не настолько, чтобы специально этим интересоваться, но которые будут рады, если им что-нибудь интересное на эту тему расскажут.
Да и, кроме того, интересных и полезных алгоритмов существует столько, что, чтобы всех их знать, надо интересоваться этим очень и очень сильно.
То есть, вы предпочли бы видеть такие статьи в более научном и серьёзном виде?
Да и, кроме того, интересных и полезных алгоритмов существует столько, что, чтобы всех их знать, надо интересоваться этим очень и очень сильно.
То есть, вы предпочли бы видеть такие статьи в более научном и серьёзном виде?
Да-да, побольше топиков про игры, популярных видеороликов и прикольных картинок, как на dirty.ru!!! Это ведь IT-ресурс, а не сайт по программированию какой-нибудь.
Чего именно? Решения такой задачи, или знания алгоритма?
Во-первых, вы сможете решить эту задачу, если с ней столкнётесь. Ведь SergeyACTIVITI в своём посте говорил лишь о удобной обёртке на питоне. Кроме того, этот алгоритм можно модифицировать. Кем-то написаный решатель решает лишь ограниченный круг задач, который в него заложен. А вы можете модифицировать алгоритм для любой ситуации.
Упаковка шмоток в дьябло! ^_^
выдача купюр в банкомате — самый тривиальный пример задачи, которую решает этот алгоритм.
Угу. Это ведь оптимальный вариант и для самого девайса и для клиента.
Насколько я знаю, номиналы банкнот и монет специально подобраны так, чтобы жадный алгоритм мог выдавать сдачу.
Жадный алгоритм работает, если номиналы банкнот последовательно делятся друг на друга. Это правда в России, но не думаю, что везде.
Это при достаточном их количестве. А вот если нужно выдать сдачей 6 рублей, а остались только монетки 5 и 2. Тогда жадный алгоримт не поможет.
Я, правда, думал, что банкоматы обычно с монетами не работают. Но всякие кофемашинки работают, Вы правы.
Забавно. Ровно на следующий день на городской личной олимпиаде Новосибирска именно такая задача и была :) Но там — разбор частных случаев и жадный алгоритм
ну для клиента зачастую важно последнюю купюру дать мелочью (6 бумажек тысячами и 2 пятисотками).
к счастью, некоторые автоматы так и делают.
к счастью, некоторые автоматы так и делают.
в ПриватБанке об этом, видимо, не знают. или знают но не доделали. у них даже диалог такой есть «Вам какими листами?». правда что бы Вы не выбирали дадут мелкими. выдать почти пачку(98) 50-к и десять 10-к когда просил «крупными» для них в порядке вещей (в наличии 200-к уверен, следующему дали 200-ки). видимо это такая разновидность внутрибанковского юмора :/
Ага) Я как пошёл снимать с карточки (Сбербанк) несколько тысяч (кажется, 7), когда на карточке должно было быть ещё порядка 50-ти. Пытаюсь снять — он говорит «Слишком большая сумма». Я делаю большие глаза, проверяю счёт — всё нормально, 50+ кр. Тогда я пытаюсь снять 1 тыщу — фигак, он мне её сотками выдаёт)) Так все 7 тыщ сотками и выдал) Сумма была слишком большая, потому что лоток не помещалась — как, впрочем, и в бумажник)
ИМХО можно было организовать гораздо проще, как я понимаю — задачка для вора, как утащить большее кол-во денег при определённом весе(объёме),
а не проще ли вычислить удельную стоимость каждой вещи, и взять те где удельная стоимость единицы объёма больше, а если одну вещь можно взять 1 раз, то вычислить удельную стоимость каждой вещи в массиве и отсортировав по убывания пойти сверху, взять те что дороже, а на остатки веса взять то что влезет.
на оригинальность и правильность не претендую, хотелось бы услышать мнение грамотных в этом деле людей.
а не проще ли вычислить удельную стоимость каждой вещи, и взять те где удельная стоимость единицы объёма больше, а если одну вещь можно взять 1 раз, то вычислить удельную стоимость каждой вещи в массиве и отсортировав по убывания пойти сверху, взять те что дороже, а на остатки веса взять то что влезет.
на оригинальность и правильность не претендую, хотелось бы услышать мнение грамотных в этом деле людей.
*убыванию
Конечно, это самая естественная мысль, но, к сожалению, неверная.
Допустим, ёмкость рюкзака равна 6. И есть два типа вещей: у первого объём 4 и стоимость 5, у второго — объём 3 и стотимость 3. Согласно Вашему алгоритму, мы возьмём одну вещь первого типа, и всё. Стоимость взятого — 5. А можно взять две вещи второго типа, стоимость — 6.
Допустим, ёмкость рюкзака равна 6. И есть два типа вещей: у первого объём 4 и стоимость 5, у второго — объём 3 и стотимость 3. Согласно Вашему алгоритму, мы возьмём одну вещь первого типа, и всё. Стоимость взятого — 5. А можно взять две вещи второго типа, стоимость — 6.
Спасибо за разъяснения, будем исправляться
Чуть-чуть подправлю: вычисляем коэффициенты, сортируем. Если коэффициенты совпали (как в приведенном примере) берем вещи с наименьшим весом.
Если требуется заполнить полностью, и больше никакая вещь не входит, то добавить подходящую по весу и считать портфель 1 решением.
Затем убрать добавленную вещь, далее убирать вещи из рюкзака до тех пор пока не войдет вещь самая высокая по коэффициенту. Если этот портфель выше по стоимости, чем первый оптимальный, то считать оптимумом его.
Если требуется заполнить полностью, и больше никакая вещь не входит, то добавить подходящую по весу и считать портфель 1 решением.
Затем убрать добавленную вещь, далее убирать вещи из рюкзака до тех пор пока не войдет вещь самая высокая по коэффициенту. Если этот портфель выше по стоимости, чем первый оптимальный, то считать оптимумом его.
Не понял, «Если требуется заполнить полностью, и больше никакая вещь не входит, то добавить подходящую по весу» — как же добавить, если больше никакая вещь не входит?
«Затем убрать добавленную вещь, далее убирать вещи из рюкзака до тех пор пока не войдет вещь самая высокая по коэффициенту.» — у нас же итак в рюкзаке только вещи с самым высоким коэфициентом?
1. И почему это работает?
2. Каково будет время работы?
«Затем убрать добавленную вещь, далее убирать вещи из рюкзака до тех пор пока не войдет вещь самая высокая по коэффициенту.» — у нас же итак в рюкзаке только вещи с самым высоким коэфициентом?
1. И почему это работает?
2. Каково будет время работы?
Хмм, как коэффициеты совпали-то в примере? 5/4 == 1.25 и 3/3 == 1. Не совпадают.
В вашем алгоритме как минимум не видно условие окончания цикла. Некоторая эвристика поверх жадного алгоритма, да, позволит найти субоптимальные решения.
Скажите, пожалуйста, что даст ваш алгоритм, например, для вещей: объём 4, вес 4 и объём 3, вес 3 — в случае рюкзака объёма 8. Мне кажется — возьмутся две более лёгкие вещи, заполнится ёмкость 6 из 8 и цену 6 достигнем, тогда как оптимум — 8.
Не стоит изобретать велосипеды, особенно плохо ездящие.
В вашем алгоритме как минимум не видно условие окончания цикла. Некоторая эвристика поверх жадного алгоритма, да, позволит найти субоптимальные решения.
Скажите, пожалуйста, что даст ваш алгоритм, например, для вещей: объём 4, вес 4 и объём 3, вес 3 — в случае рюкзака объёма 8. Мне кажется — возьмутся две более лёгкие вещи, заполнится ёмкость 6 из 8 и цену 6 достигнем, тогда как оптимум — 8.
Не стоит изобретать велосипеды, особенно плохо ездящие.
Нет, почему же, изобретать велосипеды можно и нужно, если они будут ездить лучше старых. Но перед тем, как предъявлять велосипед, надо быть уверенным, что он ездит и хотя бы не хуже старого.
Коэффициент:
отношение объема к общему объему
поделить на
отношение цены к общей цене товаров
вес отнош. цена отнош. коэф. рюкзак 8
3 0.375 3 0.75 0.5 сумма 4
4 0.5 4 1 0.5
По сути алгоритм схож со стандартным, но удобнее в восприятии. Окончание — максимум возможный в задаче.
отношение объема к общему объему
поделить на
отношение цены к общей цене товаров
вес отнош. цена отнош. коэф. рюкзак 8
3 0.375 3 0.75 0.5 сумма 4
4 0.5 4 1 0.5
По сути алгоритм схож со стандартным, но удобнее в восприятии. Окончание — максимум возможный в задаче.
Общую цену товаров мы не знаем.
Нет, он не удобнее в восприятии — Вы ведь так и не рассказали толком, в чём он заключается.
Нет, он не удобнее в восприятии — Вы ведь так и не рассказали толком, в чём он заключается.
Собственно задача:
СУММА (вес i товара в рюкзаке*цена i товара в рюкзаке)->max
допустимый вес = const
дано
цена товаров=Сумма(цена i товара)
цена_i_товара вес_i_товара коэффицент
коэффицент=(цена_i_товара/цена товаров)/(вес_i_товара/допустимый вес)
Далее — описано выше. Есть еще несколько частных граничных случаев, которые нужно учесть. Но суть все та же — перебор.
Общая цена — это цена товаров=Сумма(цена i товара).
СУММА (вес i товара в рюкзаке*цена i товара в рюкзаке)->max
допустимый вес = const
дано
цена товаров=Сумма(цена i товара)
цена_i_товара вес_i_товара коэффицент
коэффицент=(цена_i_товара/цена товаров)/(вес_i_товара/допустимый вес)
Далее — описано выше. Есть еще несколько частных граничных случаев, которые нужно учесть. Но суть все та же — перебор.
Общая цена — это цена товаров=Сумма(цена i товара).
Вы что, издеваетесь? Если бы выше было описано, я бы к Вам не приставал, а условия я и сам знаю.
И какой идеологический смысл имеет цена товаров? Можно добавить много тяжёлых и дешёвых таваров, очень много, так, что общая цена изменится радикально. А суть задачи — нет.
И какой идеологический смысл имеет цена товаров? Можно добавить много тяжёлых и дешёвых таваров, очень много, так, что общая цена изменится радикально. А суть задачи — нет.
О, кстати. Цена товара — это не за единицу веса, а за единицу товара. То есть c[i] стоит один товар, который имеет вес v[i]. Цена одного товара — c[i], а не c[i]*v[i].
Впрочем, это не меняет суть задачи.
Впрочем, это не меняет суть задачи.
Ну если я правильно таблицу понял (присоединюсь к вопросам про «общую цену», из ваших выкладок кажется, что это максимальная цена на товар), то коэффициенты и там, и там — 0.5. И следовательно, по вашим же словам, надо брать более лёгкий предмет — то бишь веса 3. Что, как уже показано контрпримером, неоптимально.
В общем случае — надо. Далее идет проверка, оптимальный ли набор товаров выбран. В большинстве случаев он будет оптимален. Два крайних случая — 1) когда рюкзак заполнен не весь и есть возможность его добить; 2) когда рюкзак заполнен, но есть альтернативы. Надо рассматривать отдельно. Но тем не менее в большинстве случаев этот алгоритм будет работать быстрее стандартного.
А в остальных — не будет работать вообще.
Ну и как Вы определяете, оптимален ли набор?
Ну и как Вы определяете, оптимален ли набор?
как определяется наличие альтернатив? ну и как рассматривать это всё отдельно придётся? вот пока по треду вышеупомянутое «удобнее в восприятии» никак не прощупывается.
большинство случаев — это хорошо, в основном это будет как раз вариант, когда у нас большой рюкзак и маленькие предметы, тогда вышеупомянутая эвристика сведёт алгоритм чуть ли не к линейному (тогда как динамический работает за O(N*W)). или для тех вариантов, когда W >> N — рюкзак настолько большой, что не помещается в памяти.
а вот зато для того, чтобы этот алгоритм работал на всех случаях входных данных, надобно подставлять костыли и подпорки, которые ни надёжности, ни понятности алгоритма не добавляют.
большинство случаев — это хорошо, в основном это будет как раз вариант, когда у нас большой рюкзак и маленькие предметы, тогда вышеупомянутая эвристика сведёт алгоритм чуть ли не к линейному (тогда как динамический работает за O(N*W)). или для тех вариантов, когда W >> N — рюкзак настолько большой, что не помещается в памяти.
а вот зато для того, чтобы этот алгоритм работал на всех случаях входных данных, надобно подставлять костыли и подпорки, которые ни надёжности, ни понятности алгоритма не добавляют.
А почему нельзя для каждой вещи высчитать соотношение объема и стоимости и максимально загрузиться вещью, с самым большим соотношением?
Задача, решение которой должен знать каждый играющий в RPG =)
Хорошая задача, классическая ;-) как мы ее в универе называли — задача о (зас)ранце, и практиковали на ней симплекс-метод ;)
Это одномерная упаковка, не так интересно.
Вчитываться в алгоритм не стал, так как (простите) такое описание алгоритмов после 2х лет лекций по Теории Алгоритмов от отличного преподавателя просто невозможно читать.
Вчитываться в алгоритм не стал, так как (простите) такое описание алгоритмов после 2х лет лекций по Теории Алгоритмов от отличного преподавателя просто невозможно читать.
Что ж, «я не червонец, чтобы нравиться всем» (с). Пост и не был рассчитан на самую искушённую публику. А где Вы учились?
В любом случае это не отменяет нечитаемость статьи. Оформите в удобочитаемый вид, добавьте реализацию алгоритма хотя бы на псевдокоде — будет намного больше пользы и, соответственно, плюсов.
Критика принята.
А реализацию-то зачем? Статья-то не о программе, а об алгоритме.
А реализацию-то зачем? Статья-то не о программе, а об алгоритме.
Да не, я без претензий :)
Учусь в МГУПИ, правда конкретно упаковку проходил вне лекций, с научным руководителем.
Если интересно, вот работа по теме
Учусь в МГУПИ, правда конкретно упаковку проходил вне лекций, с научным руководителем.
Если интересно, вот работа по теме
Можно так перса в какой-нибудь игрушке одевать с прицелом на максимальную защиту или атаку, например.
— Сынок, собрала тебе рюкзак в дорогу, положила консервы, хлеб, масло, гвозди…
— Мама, зачем?
— Ну, масло на хлебушек намажешь, с консервами скушаешь.
— Мама, а гвозди??
— Положила, сынок, положила.
— Мама, зачем?
— Ну, масло на хлебушек намажешь, с консервами скушаешь.
— Мама, а гвозди??
— Положила, сынок, положила.
Может быть стоит добавить что O(W) это псевдо-полиномиальное время, а сама проблема NP-complete? И подождите, вы же просто описали метод решения динамическим панорамированием?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача о рюкзаке: а что же внутри?