python：算法 - 从平均值中收集项目

Question

不确定这是否是正确的地方，但我有一个与算法相关的问题，我想不出一个有效的算法。 所以想分享我的问题陈述..:) 为了简化我想要解释的内容，让我创建一个假设的例子。

假设，我有一个列表，其中包含一个对象，其中包含两个东西..

lets say product id and price

现在，这是一个很长的列表..有点像库存.. 由此我定义了三个价格段..低价、中价和高价 然后是 k1,k2,k3，其中 k1,k2 和 k3 是比率。 所以，现在的工作是，我必须从这个巨大的库存中收集产品，这样有 n1 个低价产品、n2 个中价产品和 n3 个高价产品...其中 n1:n2: n3 == k1:k2:k3

现在，我如何有效地实现以下目标。 我的目标最低价是100美元 我必须从这个系列中收集 20 种产品.. 中间价格范围可能是 500 美元 等等

所以我从 100 美元开始..然后寻找 90 到 100 之间以及 100 到 110 之间的物品 假设我在区间 1 低点 (90,100) 中发现了 5 个产品，在区间 1 高点 (100,110) 中发现了 2 个产品 然后，我进入下一个低区间和下一个高区间。 我继续这样做，直到获得该时间间隔内的产品数量。

我该怎么做？也可能存在这种情况，当特定价格范围内的产品数量少于我需要的..（也许中间价格范围是 105 美元...）..那么在这种情况下我应该做什么.. 请原谅我，如果这不是正确的平台……从这个问题中您可以看出这更像是一个辩论性问题，而不是“我收到此错误”类型的问题。 谢谢

Answer 1

您可能正在寻找选择算法。

首先找到n1第一个最小元素，设其为e1，下界列表就是满足的所有元素>元素<= e1。

对其他范围执行相同的操作。

下界列表的伪代码：

getLowerRange(list,n):
  e <- select(list,n) 
  result <- []
  for each element in list:
     if element <= e:
         result.append(element)
  return result

注意，如果有许多“相同”项目[结果将是一个更大的列表]，则此解决方案将失败，但找到这些项目并将其从结果列表中删除并不困难。

请注意，选择算法的复杂度为O(n)，因此该算法将消耗与列表大小相关的线性时间。

Answer 2

方法 1

如果分配哪些产品属于三个价格段永远不会改变，那么您为什么不简单地构建 3 个列表，一个列表用于每个价格段中的产品（假设这些集合是不相交的）。
然后您可以从这些列表中随机选择（带或不带替换 -随你便）。每个类别的项目数量由比率给出。

方法 2

如果要预先指定产品价格段分配，例如，通过在函数调用时传递每个段的相应价格值，您可能希望按价格对产品进行排序，并且使用二分搜索来选择m-nearest-neighbors（对于 例子）。参数m可以根据比率指定。如果您指定最大距离，您可能会拒绝超出所需价格范围的产品。

方法 3

如果需要自主确定产品价格段分配，您可以应用k-means，进行分配你的产品，比如说， k = 3 价格段。对于实际的产品选择，您可以按照上述类似的方式进行。

Answer 3

看来您应该尝试数据库解决方案而不是使用列表。查看 sqlite。默认情况下是Python