如何找到基于多个变量的计算的最低值？

Question

注意:我正在使用ColdFusion，但我觉得这可以涵盖广泛的语言，因为这更多地是一个编程问题，而不仅仅是一个ColdFusion问题。

好的，我的任务是实现代码，将促销应用于购物车中的项目。基本上，可以对任意数量的项目进行任何数量的促销--即“购买2项'ABC'，得到1个项目'ABC‘50%的折扣”。然而，也可以有“购买3的项目'ABC'，得到一个项目'ABC‘免费。”甚至“买2个项目的'ABC'，得到1个项目'XYZ‘50%的折扣”。

所以，想象一下在广泛的产品中有更多这样的促销活动。

现在，我需要遍历所有可能的场景，以应用给客户提供最佳价值(最低小计)的促销(或promotionS)。

但是，我不知道如何编写贯穿所有可能场景的代码。我可以通过过滤那些不适用于购物车中的商品来缩小符合条件的促销数量。很明显，我也知道购物车里有多少符合条件的物品。

因此，假设我在我的手推车中有5件物品，其中3件有合格的促销(如上面的那些)。1项有3项可能的晋升，另一项有4项可能的晋升，另一项有2项可能的晋升。我的第一个想法是，在每一种可能的促销中循环，在该循环中，通过每一种可能的合格项目顺序循环：

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

...and每次都应用促销，保存产生最低小计的组合.

这个能行吗？是不是太过分了？有人有更好的建议吗？

任何代码示例都将不胜感激。虽然我正在用ColdFusion编写程序，但我可以很好地阅读/理解其他语言。

谢谢。

Answer 1

而不是循环浏览项目和寻找组合，你可以循环通过促销和模式匹配与购物车，也许更容易？

或者你可以优先考虑晋升，如果一个总是比另一个优越的话？因此，如果一个申请，你可以跳过所有的晋升，而不太优先？

Answer 2

这似乎是个搜索问题。每个问题都是搜索问题。我会从一个简单的深度优先搜索开始，因为这消耗了很少的内存。

下面是一些深度优先搜索的伪代码.

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(晋升))。

如果搜索时间太长，我建议将其修改为分支和绑定搜索，并将促销从最大到最小排序。

Answer 3

基于@Henry的回答，我认为解决方案取决于如何处理晋升问题。在以下情况下，这很可能是最优解决的：

1. 对于某一特定类型的促销活动(例如，购买一次得到一次)，可以应用于订单的数量没有限制。
2. 一个促销项目的数量是有限的(不买一个全价，得到你想要的半价)，数量越多，单位成本就越低。
3. 促销只适用于一种“类型”的商品，而一种产品只适用于一种类型(如书籍)。

#2中的点用于确定“优先级”，这样一个算法将按该类型的类型和数量对项进行分组，并在这些组中迭代以找到适用的推广。

现在，如果上面提到的是不真实的，我认为您现在正在处理一个问题，在没有找到所有其他解决方案的情况下，不可能断言要花多长时间才能得到“最佳”解决方案。现在，如果项目数量很小，这可能是可行的，找到每一种可能性，并选择最低的成本，但我认为，数量的可能性成倍增长的基础上，项目的数量和可能的促销。我认为这是一个NP完全问题。

相反，您需要一个在合理的时间内产生“好”解决方案的算法。如果是这样的话，我认为一种名为模拟退火的方法是适用的:基本上是一种在任意次数中迭代的算法(您需要进行测试，以找到性能上可以接受的值)。该算法是随机种子输入，在这种情况下，适用的晋升。该算法返回总成本。每次迭代都会改变算法的输入--整个算法的一部分是查找产生“好”结果的两个迭代，并将它们的输入组合到另一个迭代中。