代码之家  ›  专栏  ›  技术社区  ›  Ozzy

PHP计算平衡数组

  •  4
  • Ozzy  · 技术社区  · 15 年前

    好吧,我不确定标题是否有效,但我能想出的最好的标题。

    基本上是这样的。

    我有11个类别。在每个类别中,我都有项目,但一个类别可能有1个项目,1个类别可能有20个。

    现在,我想将11个类别分为5个堆栈或列。

    我希望每个堆栈包含等量或几乎等量的项,并且没有类别项可以溢出堆栈。

    因此,考虑到以下数据:

    Category | Items
    -------------------------
    Cat 1 | 10 
    Cat 2 | 3 
    Cat 3 | 7 
    Cat 4 | 11 
    Cat 5 | 5 
    Cat 6 | 13
    Cat 7 | 19 
    Cat 8 | 5  
    Cat 9 | 3 
    Cat 10 | 9 
    Cat 10 | 15
    
    Total = 100 Items 
    

    所以我希望这些物品能均匀地分布在书堆中。

    共有5个堆叠,因此要相等,每个堆叠应该有20个项目。但问题是,一个堆栈中的项不能溢出。那么,我如何计算数据以输出如下内容:

    Stack 1|Stack 2|Stack 3|Stack 4|Stack 5
    -------|-------|-------|-------|-------
    Cat 10 |Cat 1  |Cat 11 |Cat 6  |Cat 7
    Cat 4  |Cat 3  |Cat 8  |Cat 9  |
           |Cat 2  |       |Cat 5  |
    
    20      20      20      21      19
    

    只要项目在堆栈中分布得最均匀,那么哪个类别的堆栈就无关紧要。

    现在,这个堆栈计算的结果将被缓存,因为我不需要经常计算,所以如果解决方案的CPU很重,仍然可以发布它。

    谢谢)

    1 回复  |  直到 15 年前
        1
  •  1
  •   null_radix    15 年前

    这是背包问题。 http://en.wikipedia.org/wiki/Knapsack_problem 有很多资源是你谷歌背包的问题

    一个简单的方法是尝试所有可能的组合。您计算的每个组合也将计算标准偏差。使用标准偏差保存最佳拟合组合。