算法临界点

Question

我是一个完整的算法笨蛋，我遇到了这个问题，我需要通过单价或批量购买 x 小部件来找到购买未知数量小部件的最低成本......一个例子会帮助我'我确定:-

1) 每件小部件价格为 0.05 美元2) 小部件批量价格为每 100 个小部件 4.00 美元

假设我想购买 140 个小部件 -

a) 按单位计算成本是 140 x $0.05c => $7.00b) 按批计算成本是 2 批 100 @ $4.00 => $8.00(多余的 60 个小部件可以忽略)

所以在这种情况下按单位购买会便宜 $1.00

但是，如果我想购买 190 个小部件，那么 -

a) 按单位计算成本是 190 x $0.05c => $9.50b) 按批计算成本是 2 批 100 @ $4.00 => $8.00(多余的 10 个小部件可以忽略)

这种情况下批量购买价格更便宜...

所以我需要找出如何以编程方式找出两种方法之间的“临界点”在哪里以获得最便宜的价格。

我希望我已经解释清楚了，我确信这是一个简单的答案，但我今天的大脑很快就退色了!

TIA

编辑::

好的，抱歉——我意识到我没有说清楚——因为有人指出批处理和单位的混合也是可能的，所以对于 140 个小部件示例，它也可以是 1 个批处理和 40 个单位.

我想要实现的是以编程方式找到购买 X 个小部件的最便宜方式，每个小部件的价格为 $XX，并且还给出了 NN 个小部件的批量价格 $YY。

购买一批多余的小部件没有问题，即可以多于 X 次购买，但不能少于 X 次

所以对于 140 个示例，1 批 @ 4.00 美元 + 40 件 @ 0.05 美元 => 6.00 美元，这是我认为最便宜的。和对于 190 个示例，我认为 2 个批处理仍然是最便宜的，因为 1 个批处理 + 90 个单位是 8.50 美元...

我希望那里有一些简洁的方程式可以做到这一点:)

Answer 1

我用 Python 编写了一个基本的暴力风格脚本来比较两个选项的价格(最多 1,000 个元素)。这不是最快也不是最优雅的方法，但它似乎有效。

输出格式为:(<unit-count>, (<per-unit-cost>, <per-batch-cost>))

import math
import itertools
import pprint

unitList = range(1000)
pricePerUnit = .05
pricePerBatch = 4.0
numberPerBatch = 100.0

def calculatePerUnit(units):
  """ Calculate the price of buying per unit
  """
  return units * pricePerUnit

def calculatePerBatch(units):
  """ Calculate the price of buying per batch
  """
  return math.ceil(units / numberPerBatch) * pricePerBatch

def main():
  """ Execute the script
  """
  perUnit = map(calculatePerUnit, unitList)
  perBatch = map(calculatePerBatch, unitList)
  comparisonList = zip(perUnit, perBatch)
  perUnitCheaperPriceList = list(itertools.ifilter(lambda x: x[0] < x[1], comparisonList))
  perUnitCheaperUnitList = map(lambda x: int(x[0] / .05), perUnitCheaperPriceList)                                                                              
  pprint.pprint(zip(perUnitCheaperUnitList, perUnitCheaperPriceList))

if __name__=="__main__":
  main()

结果:

[gizmo@test ~]$ python TippingPoint.py 
[(1, (0.050000000000000003, 4.0)),
 ... These are sequential values I left out for brevity ...
 (79, (3.9500000000000002, 4.0)),
 (101, (5.0500000000000007, 8.0)),
 ... These are sequential values I left out for brevity ...
 (159, (7.9500000000000002, 8.0)),
 (201, (10.050000000000001, 12.0)),
 ... These are sequential values I left out for brevity ...
 (239, (11.950000000000001, 12.0)),
 (301, (15.050000000000001, 16.0)),
 ... These are sequential values I left out for brevity ...
 (319, (15.950000000000001, 16.0))]