Задача о применении нескольких скидок
На первый взгляд напоминает задачу о рюкзаке.
Сомневаюсь, что тут удастся сильно сократить сложность в общем случае, особенно в случае с скидками типа "15% на каждый товар, цена которого численно равна сумме скидок на предыдущие товары"
Сомневаюсь, что тут удастся сильно сократить сложность в общем случае, особенно в случае с скидками типа "15% на каждый товар, цена которого численно равна сумме скидок на предыдущие товары"
Она много что напоминает - и Rete, и поиск минимального пути, но всё не то.
1. что в точности есть "скидка"?
2. какие правила о применении двух (и более) скидок?
2. какие правила о применении двух (и более) скидок?
1) на каждый товар может действовать только одна скидкаЯ что-то не понял, насчёт порядка скидок. Если есть скидка на каждый товар (малая) и скидка на каждый третий товар (большая), то по правилу "одна скидка на товар" мы будем иметь, что в независимости от порядка, 3 товара пойдут с большой скидкой и 7 товаров с малой.
2) результат может зависеть от порядка применения скидок (например есть 10 одинаковых товаров по цене X и скидка 10% на них всех и скидка 60% на каждый 3ий товар. если применяем сначала вторую, а потом первую, то получаем в итоге {1 - [6 * 1 + 3 * (100 - 60)/100 + 1 * (100 - 10)/100]/10} * 100 = 19%, а если сначала первую, то вторую не к чему применять уже будет)
Мне кажется, тебе для начала стоит формализовать понятие скидки. Ты его ввёл через пример, притом не очень ясный. Объясни сразу что такое скидка, каковы правила применения скидки к товару и к набору товаров, и тогда, скорее всего, тебе даже придётся обращаться к форуму за помощью в алгоритмах - сам всё поймёшь.
На всякий случай, если на скорость насрать, а хочется гибкости - рекомендую почитать attribute grammar
Скидка - чёрный ящик, который пропускает через себя корзину товаров и на выходе помечает те товары, на которые она подействовала и возвращает результирующую цену после применения себя. Уже помеченные предметы она не затрагивает.
Мне показалось, что в примере понятно, что скидка 60% на каждый третий товар затрагивает(помечает) все девять товаров, а не три, как хотелось бы. Иначе, было бы слишком халявно.
З.Ы. заканчивай с высокопарностью.
Мне показалось, что в примере понятно, что скидка 60% на каждый третий товар затрагивает(помечает) все девять товаров, а не три, как хотелось бы. Иначе, было бы слишком халявно.
З.Ы. заканчивай с высокопарностью.
Может быть скидка "купи к товару в корзине аксессуар со скидкой X%", которая будет соответственно помечать оба товара в корзине (если таковые зарезервированные пары там есть) и давать скидку на аксессуар.
Скидка - чёрный ящик, который пропускает через себя корзину товаров и на выходе помечает те товары, на которые она подействовала и возвращает результирующую ценуну очевидно же, что ничего, кроме перебора быть не может, если больше никаких свойств "скидок" не известно.
Скидка - чёрный ящик, который пропускает через себя корзину товаров и на выходе помечает те товары, на которые она подействовала и возвращает результирующую цену после применения себяперебор чёрных ящиков тебя ждёт.
Если нет никаких функций сохранения, то глупо рассчитывать на улучшение времени.
Если нет никаких функций сохранениятебя же попросили
ну, можно допустим брать представление помеченных товаров в виде 011010 и запоминать цену для такого сочетания, и если в другой ветке встретится такое же сочетание, или подходящее под wildcard ?11?1?, с худшим результатом, то отбрасывать вычисление ветки.
ну очевидно жеЧто, и доказательство сможешь вывести?
с доказательством не знаю, природу не обманешь. Это всё равно, что пытаться при архивировании всегда получать файлы меньшего размера. Если ты не переберёшь всё, то ты просто не сможешь узнать какая комбинация лучше
Что, и доказательство сможешь вывести?оптимизация функции-черного ящика без свойств. Просто допустим ты не рассмотрел один вариант применения скидок. Если скидки не должны удовлетворять никаким свойствам, а являются настоящими черными ящиками, то можно изменить их поведение так, чтобы они на всех вариантах их применения давали те же результаты, на этом одном — другой, более эффективный. Вот и доказательство.
Сомневаюсь, что тут удастся сильно сократить сложность в общем случае, особенно в случае с скидками типа "15% на каждый товар, цена которого численно равна сумме скидок на предыдущие товары"всё-таки есть ещё одно свойство: она никак не зависит от предыдущих скидок и зависит только от оставшихся (непомеченных) товаров.
В этой фразе есть противоречие. Конфигурация непомеченных товаров зависит от применения предыдущих скидок
Если есть только одна скидка, которая действует на каждый третий товар, то итоговая стоимость зависит от того, в каком порядке товары лежат в корзине, да?
Если есть только одна скидка, которая действует на каждый третий товар, то итоговая стоимость зависит от того, в каком порядке товары лежат в корзине, да?Конечно. Но мы даём скидку на div 3 самых дорогих товаров. Клиент, как говорится, всегда прав.
В этой фразе есть противоречие. Конфигурация непомеченных товаров зависит от применения предыдущих скидокПротиворечия нет. Не важно, сколько товаров уже есть в корзине, мы смотрим только на непомеченные, как будто в корзине есть только они.
да это пожалуйста. Но тебе реально понадобится перебрать все возможные разбиения. Ведь цена каждого разбиения - чёрный ящик и известно только, что зависит от поступившего на вход множества. Бесперспективно. Я бы мог ещё порекомендовать эвристику, но даже для эвристики нужно знать хоть какую-то статистику по чёрным ящикам.
Имхо, тебе всё же надо разобраться в правилах скидок. Могу предложить тебе подумать над вот таким ограничением: цена любого комплекта товаров при применении скидки не может быть больше чем цена тех же товаров, дополненных ещё одним товаром.
Имхо, тебе всё же надо разобраться в правилах скидок. Могу предложить тебе подумать над вот таким ограничением: цена любого комплекта товаров при применении скидки не может быть больше чем цена тех же товаров, дополненных ещё одним товаром.
Могу предложить тебе подумать над вот таким ограничением: цена любого комплекта товаров при применении скидки не может быть больше чем цена тех же товаров, дополненных ещё одним товаром.Я об этом уже писал другими словами:
ты писал какой-то малосвязный бред. Ещё десяток постов выше ты признался, что видишь механизм скидок как сплошной чёрный ящик. И с тех пор, вроде бы, самостоятельно не смог продвинуться в деле формализации своих неясных знаний о механизме скидок. Так что, повторюсь, перестань трясти стену, забей на алгоритмы пока, попробуй нормальную формализацию разработать для своей задачи.
Ничего не бред. Попробуй иногда выключать математика и включать рациональную логику. Я тут ещё поразмышлял на эту тему, и пришёл к одному очень важному выводу: скидка определённого типа на m продуктов не может быть больше чем такая же скидка на m+1 продукт. А отсюда легко прийти к заключению, что достаточно просто "жадного" алгоритма, т.е. операций вычисления скидки будет максимум треугольное число т.е. сложность n^2.
Попробуй иногда выключать математика и включать рациональную логику.у тебя какое-то превратное понимание математики
Ну а ты где-нибудь видел слоган "купите одну банку вместо двух и получите скидку!" или чтобы оптом было дороже, чем в розницу?
слушай, мат. модель должен был построить ты сам. А потом уже на позитиве спрашивать об алгоритмах.
И ты, кажется, не понимаешь, что математика больше любой другой науки посвящена рациональной логике. Собственного предмета для научного изучения у неё вовсе нет.
И ты, кажется, не понимаешь, что математика больше любой другой науки посвящена рациональной логике. Собственного предмета для научного изучения у неё вовсе нет.
Ты забываешь, что здесь раздел не про математику. А программы в большинстве своём (за исключением всяких маткадов) описывают сущности из реального мира. Свойства которых ты знаешь с детства и можешь пощупать или увидеть. И вариантов, как их декомпозировать на более мелкие задачи, классы, и пр. больше одного. Тут люди этим на хлеб зарабатывают. Если человек спросит, как домик на экране нарисовать, ты же не будешь его посылать за математическим определением дома.
З.Ы. в общем как обычно на ФЛ - сам на свой вопрос ответил, а разговор постепенно скатывается в холивар.
З.Ы. в общем как обычно на ФЛ - сам на свой вопрос ответил, а разговор постепенно скатывается в холивар.
цена любого комплекта товаров при применении скидки не может быть больше чем цена тех же товаров, дополненных ещё одним товаром.это утверждение записывается как, T - скидка < T+T1, где все переменные неотрицательные. И получается, что оно всегда тавтологично.
Если есть только одна скидка, которая действует на каждый третий товар, то итоговая стоимость зависит от того, в каком порядке товары лежат в корзине, да?Получается, надо перебрать не только все варианты скидок (N!), но и всевозможные положения товаров в корзине (M!)
Конечно. Но мы даём скидку на div 3 самых дорогих товаров. Клиент, как говорится, всегда прав.
Допустим, есть
скидка 1 - 30% а каждый третий товар и
скидка 2 - 15% на каждый второй товар.
Как выгоднее всего расположить товары в корзине?
Мне кажется надо ввести разумные ограничения и формализовать скидку (например, исключить бредовые ситуации когда скидка зависит от того как товары лежат в корзине)
А программы в большинстве своём (за исключением всяких маткадов) описывают сущности из реального мира.да. Но вот момент. Программы не имеют никакого отношения к естественному языку. Для описания сущностей реального мира в программах необходим язык математики
это утверждение записывается как, T - скидка < T+T1, где все переменные неотрицательные. И получается, что оно всегда тавтологично.ты кажется решил опираться на какое-то интуитивное определение скидки. Я, собственно, и ввёл это правило, чтобы интуитивное понимание скидки отразить.
Вот почитай как скидку определил автор топика:
Скидка - чёрный ящик, который пропускает через себя корзину товаров и на выходе помечает те товары, на которые она подействовала и возвращает результирующую цену после применения себя.Каким образом получается тавтология?
З.Ы. в общем как обычно на ФЛ - сам на свой вопрос ответил, а разговор постепенно скатывается в холивар.ну так ты бы не называл свой вопрос задачей. А так человек читает заголовок "задача" и ожидает задачу, а внутри вынос мозга.
P.S. согласно интуитивному определению жадный алгоритм на справится, но я всё ещё жду точного определения задачи.
Судя твоей логике, работа аналитика вообще сплошной вынос мозга. И ничего, живут как-то люди, депрессии и самоубийства у них не чаще, чем у других.
если аналитик вынужден интервьюировать тупых непоследовательных людей, не способных связно излагать собственные мысли, а может и вовсе их не имеющих, то я соглашусь с твоей оценкой в том, что работа аналитика - сплошной вынос мозга
Я, собственно, и ввёл это правило, чтобы интуитивное понимание скидки отразить.есть общеупотребительное понимание понятия скидка
скидка - уменьшение цены на комплект товаров на основе произвольного правила.
Твое определение является сильным ослаблением этого определения, поэтому оно и является тавтологичным.
есть общеупотребительное понимание понятия скидкаклёво, да. Но у топик стартера оно было совсем другим. О чём и речь.
Но у топик стартера оно было совсем другим. О чём и речь.prooflink?
prooflink?
ты додумываешь. ты додумал, что ТС этим пояснением отменил общеупотребительное понятие скидки (хотя ТС говорил лишь об уточнении(сужении) общеупотребительного понятия скидки до своего)
там говорится совершенно о другом.
есть S1(T1) и S2(T2),
где Sx(Tx) - это правило скидки Sx, примененное к набору товаров Tx
утверждается, что T1 и T2 не могут иметь общих товаров
соответственно, если покупатель взял три товара и у него есть две скидки:
каждый третий товар бесплатно,
20% на один товар,
то покупатель сможет воспользоваться только одной из них.
там говорится совершенно о другом.
есть S1(T1) и S2(T2),
где Sx(Tx) - это правило скидки Sx, примененное к набору товаров Tx
утверждается, что T1 и T2 не могут иметь общих товаров
соответственно, если покупатель взял три товара и у него есть две скидки:
каждый третий товар бесплатно,
20% на один товар,
то покупатель сможет воспользоваться только одной из них.
там говорится совершенно о другом.это во втором абзаце.
В первом:
Скидка - чёрный ящик, который пропускает через себя (вход: прим. комментатора) корзину товаров и на выходе помечает те товары, на которые она подействовала и возвращает результирующую цену после применения себя. Уже помеченные предметы она не затрагивает.Заметь, тут даже об отсутствии сайд-эффектов ничего не сказано, кстати зная этих горе скриптеров, они вполне могут быть. Тут, блин, даже не сказано, каким образом скидка выбирает на какое подмножество товаров она действует.
Когда задача формулируется таким образом, решить её невозможно
В первом:тоже самое что и во втором, только более коряво сформулировано.
хорошо. Возможно я слепой. Покажи мне, где написано, что результирующая цена не может увеличиться? И вообще откуда один чёрный ящик берёт цену, которую сгенерил предыдущий чёрный ящик или он вообще свою цену считает без оглядки на исходную? Как вообще цепочку-то строить?
Покажи мне где написано, что чёрный ящик скидки принимает на вход подмножество товаров, к которым скидка должна быть применена. Если это никаким образом нельзя задать, то как тогда вообще оптимизировать? Перебрать все перестановки за экспоненциальное время от фильтров?
Покажи мне где написано, что чёрный ящик скидки принимает на вход подмножество товаров, к которым скидка должна быть применена. Если это никаким образом нельзя задать, то как тогда вообще оптимизировать? Перебрать все перестановки за экспоненциальное время от фильтров?
Покажи мне, где написано, что результирующая цена не может увеличиться?указанием понятия "скидка".
ps
Встречное предложение: покажи где вообще написано, что символы выданные ТС следует трактовать как русский язык?
Покажи мне где написано, что чёрный ящик скидки принимает на вход подмножество товаров, к которым скидка должна быть применена.ты мешаешь в кучу "возможность применения скидки" и "примененную скидку".
В данном случае речь еще идет о возможности применения скидки
Перебрать все перестановки за экспоненциальное время от фильтров?тут тебя тоже заносит. Вроде до этого речь шла еще только о постановке задачи. А ты уже начинаешь заявлять, что постановка задачи неправильная, потому что мол я не знаю как такую постановку задачи решить быстро.
В данном случае речь еще идет о возможности применения скидки
Скидка - чёрный ящик,Тогда надо было бы сказать, возможность применения скидки - это чёрный ящик. Но топикстартер сказал совсем другое. Я понимаю, что за это время все читатели темы, кроме оригинального писателя, уже смогли составить своё представление о конечной цели, и даже готовы предложить несколько формализаций, но зачем устраивать соревнования по телепатии и подтирании слюней? Тем более что все наши предложения могут оказаться не в тему, если у топикстартера окажется несовместимый бизнес-процесс и способы вычисления того самого чёрного ящика.
А ты уже начинаешь заявлять, что постановка задачи неправильная, потому что мол я не знаю как такую постановку задачи решить быстро.Если ты почитаешь самый первый пост в теме, то обнаружишь, что ограничения по производительности - единственное, что удалось внятно сформулировать топикстартеру.
Вчера видел квас продавали:
0.3 - 10 руб.
0.5 - 16 руб.
1.5 - 55 руб.
0.3 - 10 руб.
0.5 - 16 руб.
1.5 - 55 руб.
это три разных sku как бы, если что. 
Оставить комментарий
kill-still
Есть M товаров. К ним можно применять N скидок.1) на каждый товар может действовать только одна скидка
2) результат может зависеть от порядка применения скидок (например есть 10 одинаковых товаров по цене X и скидка 10% на них всех и скидка 60% на каждый 3ий товар. если применяем сначала вторую, а потом первую, то получаем в итоге {1 - [6 * 1 + 3 * (100 - 60)/100 + 1 * (100 - 10)/100]/10} * 100 = 19%, а если сначала первую, то вторую не к чему применять уже будет)
Надо выбрать такой набор скидок и порядок их применения, чтобы результирующая стоимость была минимальная.
В случае полного перебора сложность M*N! очень уж сильно быстро растёт с N, так что надо придумать что-то более интересное.
Есть идеи?