如何根据多个变量找到计算的最低值？

发布于 2024-10-20 18:00:56 字数 786 浏览 1 评论 0原文

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

好的，我的任务是实现代码以将促销应用于购物车中的商品。基本上，可以对任意数量的商品进行任意数量的促销 - 即“购买 2 件商品‘ABC’，获得 1 件‘ABC’商品 50% 折扣”。然而，也可以是“购买3商品'ABC'，免费获得商品'ABC'1”。或者甚至“购买 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 中进行编程的，但我可以很好地阅读/理解其他语言。

谢谢。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

べ映画 2024-10-27 18:00:56

您可以循环浏览促销活动并与购物车进行模式匹配，而不是循环浏览商品并寻找组合，也许更容易？

或者，也许您可以为促销分配优先级，如果其中一项始终优于另一项？那么如果申请了一项，就可以跳过所有优先级较低的促销活动吗？

回复收藏 0 原文

微暖i 2024-10-27 18:00:56

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

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

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(促销))。

如果此搜索花费的时间太长，我建议将其修改为分支定界搜索，并按从最大到最小的顺序对促销进行排序。

It seems like a search problem. Well, every problem is a search problem. I would start with a simple depth-first search since that uses up little memory.

Below is some pseudo code for the depth-first search.

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, [])

The code above assumes that a promotion can only be applied once. Changing to allow multiple applications of the same promotion should be simple.

The code checks all possible orderings of all legal (canApply) promotions and finds the one that gives the lowest cost to the given 'cart'. This will take O(2^len(promotions)).

If this search takes too long I would recommend modifying it to a branch-and-bound search and ordering the promotions from biggest to smallest.

回复收藏 0 原文

寒冷纷飞旳雪 2024-10-27 18:00:56

基于@Henry 的答案，我认为解决方案取决于促销的处理方式。如果满足以下条件，则每次都可以最佳解决此问题：

可应用于订单的给定类型（例如买一送一）的促销数量没有限制给定
促销适用的商品数量是有限的（无购买）一个全价并获得任意数量的半价），数量越大，每单位成本越低，
促销仅适用于一种“类型”的商品，并且商品仅属于一种类型（例如书籍）。

#2 中的点用于确定“优先级”，以便算法按类型和该类型的数量对项目进行分组，并迭代这些组以查找适用的促销。

现在，如果上面提到的内容是不真实，我认为您现在正在处理一个问题，在没有找到所有其他解决方案的情况下，无法断言需要多长时间才能达到“最佳”解决方案。现在，如果商品数量很少，那么找到每种可能性并选择最低成本可能是可行的，但我想可能性的数量会根据商品数量和可能的促销数量呈指数增长。我将其称为NP 完全问题。

相反，您需要一种能够在合理的时间内产生“良好”解决方案的算法。如果这是真的，我认为一种名为模拟退火的方法是适用的：基本上是一种通过某种任意迭代进行迭代的算法次数（您需要进行测试以找到性能可接受的值）。该算法使用输入随机播种，在本例中适用促销。该算法返回总成本。每次迭代都会更改算法的输入 - 整个算法的一部分是找到产生“良好”结果的两次迭代，并将其输入组合用于另一次迭代。