Как найти наименьшее значение расчета на основе нескольких переменных? - PullRequest
Новая
       13

Как найти наименьшее значение расчета на основе нескольких переменных?

3 голосов
/ 04 марта 2011

Предостережение: я использую ColdFusion, но я чувствую, что это может охватывать широкий круг языков, так как это больше вопрос программирования, а не просто вопрос ColdFusion.

Хорошо, я былпоручено внедрение кода для применения рекламных акций к товарам в корзине.В принципе, может быть любое количество акций для любого количества предметов - например, «Купи 2 предмета« ABC », получи 1 предмета« ABC »со скидкой 50%».Тем не менее, также может быть «купить 3 предмета« ABC », получить 1 предмета« ABC »бесплатно».Или даже «купите 2 предмета« ABC », получите 1 предмета« XYZ »с 50% скидкой».

Итак, представьте себе, что в широком спектре продуктов проводятся подобные акции.

Теперь мне нужно пройтись по каждому возможному сценарию, чтобы применить рекламную акцию (или рекламные акции), которые дают клиенту наилучшее возможное значение (наименьшая общая сумма).

Однако я не могу понять, какнапишите код, который будет работать через любой возможный сценарий.Я могу сузить число рекламных акций, на которые можно претендовать, отфильтровывая те, которые не относятся к товарам в корзине.Очевидно, я также знаю количество подходящих товаров в корзине.

Итак, допустим, у меня в корзине 5 товаров, и у 3 из них есть соответствующие акции (например, те, что указаны выше).1 товар имеет 3 возможных продвижения, другой - 4 возможных, другой - 2 возможных.Моя первая мысль - циклически проходить каждое возможное повышение и внутри этого цикла проходить через каждый возможный порядок подходящих предметов:

1-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1

... и применяйте акции каждый раз, сохраняя комбинацию, которая дает наименьший промежуточный итог.

Будет ли это работать?Это излишне?У кого-нибудь есть лучшее предложение?

Любые примеры кода будут с благодарностью.Хотя я программирую это в ColdFusion, я прекрасно умею читать / понимать другие языки.

Спасибо.

Ответы [ 3 ]

3 голосов
/ 04 марта 2011

Вместо того, чтобы перебирать элементы и искать комбинации, вы можете циклически проходить акции и сопоставлять шаблоны с корзиной покупок, может быть, проще?

Или, возможно, вы можете назначить приоритет акциям, если они всегдапревосходит другой?Таким образом, если один из них применяется, вы можете пропустить все акции с более низким приоритетом?

2 голосов
/ 04 марта 2011

Кажется, это проблема поиска. Ну, каждая проблема - это проблема поиска. Я бы начал с простого поиска в глубину, так как он занимает мало памяти.

Ниже приведен псевдокод для поиска в глубину. 

def bestSetOfPromotions(cart, promotions, applied-promotions):
    if (len(promotions) == 0):     #no more choices
        return applied-promotions
    best-set = [] #best set of promotions found so far, the empty set.
    for next-promotion in promotions:
        if canApply(next-promotion, cart, applied-promotions):
            best = bestSetOfPromotions(cart, promotions.remove(next-promotion), applied-promotions.push(next-promotion))
            if (costOf(cart, best) < costOf(cart,best-set)):
               best-set = best
    return best-set

#we call it as such:
bestSetOfPromotions(cart, allThePromotions, [])

Приведенный выше код предполагает, что продвижение может быть применено только один раз. Изменение нескольких приложений для одной акции должно быть простым.

Код проверяет все возможные заказы всех законных (canApply) рекламных акций и находит тот, который дает наименьшую стоимость для данной «корзины». Это займет O (2 ^ len (продвижение)).

Если этот поиск занимает слишком много времени, я бы порекомендовал изменить его на поиск по веткам и по порядку и упорядочить рекламные акции от самых больших до самых маленьких.

1 голос
/ 04 марта 2011

Опираясь на ответ @ Генри, я думаю, что решение зависит от того, как продвигаются акции.Это, вероятно, оптимально решаемо каждый раз, когда:

  1. нет ограничения на количество рекламных акций данного типа (например, купить один, получить один), которые могут быть применены к заказу
  2. количество предметов, к которым относится данная акция, является конечным (не покупайте одну полную цену и не получайте столько, сколько хотите, наполовину), и чем больше это число, тем ниже стоимость за единицу товара
  3. , к которой относится только акцияодин «тип» предмета и предмет только одного типа (например, книги).

Точка в # 2 используется для определения «приоритета», так что алгоритм будет группировать элементы по типу и номеру этого типа и выполнять итерацию по этим группам, чтобы найти подходящие предложения.

Теперь, если то, что отмечено выше, является неправдой Я думаю, что вы сейчас сталкиваетесь с проблемой, когда невозможно утверждать, сколько времени потребуется, чтобы прийти к "лучшему" решению, отсутствующему при нахождении каждогодругое решение, а также.Теперь, если количество товаров невелико, возможно, будет возможно найти любую возможность и выбрать самую низкую стоимость, но я полагаю, что количество возможностей растет в геометрической прогрессии в зависимости от количества товаров и количества возможных рекламных акций.Я бы назвал это проблемой NP complete .

Вместо этого вам нужен алгоритм, который производит «хорошие» решения за разумное время.Если это правда, я думаю, что подход, называемый имитация отжига , применим: в основном алгоритм, который повторяется какое-то произвольное количество раз (вам нужно протестировать, чтобы найти значение, приемлемое с точки зрения производительности).Алгоритм посеян случайным образом с входными данными, в данном случае применимы акции.Алгоритм возвращает общую стоимость.Каждая итерация изменяет входные данные алгоритма - когда часть общего алгоритма находит две итерации, которые дали «хороший» результат, и принимает комбинацию их входных данных для другой итерации.

...