N非重叠最佳分区

Question

这是我前几天遇到的一个问题。 给定一个整数项目列表，我们希望将项目分割成至多N个不重叠的连续块，以最小化任何块中项目的最大数量的方式。 例如，假设我们给出了项目（5,2,3,6,1,6），我们需要3个bin。我们可以如下最佳划分这些：

• Ñ：1，2（2项）
• =正：3，5（2项）
• = N：6,6（2项）

每个箱具有2项，所以我们不能做任何比这更好的。 任何人都可以分享你对这个问题的想法吗？

Answer 1

鉴于n箱和p项的数组，这里是一个贪婪的算法，你可以使用。

为了尽量减少项目的最大数量在斌：

• p <= n尝试使用p箱。

  只需尝试并将每个项目放在它自己的垃圾箱中。如果你有重复的数字，那么你的平均值将不可避免地更糟糕。

• p > n贪婪地使用所有的垃圾箱，但尽量保持每个人的成员数近floor(p/n)。

  1. 组重复号码
  2. 垫功亏一篑的floor(p/n)与独特数字，左，右（如果​​存在的话）的最大重复箱。

  3. 计算您拥有的垃圾箱数量并确定您需要进行的数量合并，我们将其称为r。

     重复下列r时间：

     • 检查每一个可能的相邻分级配对;找到并执行最小合并

例

• {1,5,6,9,8,8,6,2,5,4,7,5,2,4,5,3,2,8,7,5} 20项4米仓
• {1}{2, 2, 2}{3}{4, 4}{5, 5, 5, 5, 5}{6, 6}{7, 7}{8, 8, 8}{9} 1.排序和分组
• {1, 2, 2, 2, 3}{4, 4}{5, 5, 5, 5, 5}{6, 6}{7, 7}{8, 8, 8, 9} 2。由最大的团体贪婪捕获
• {1, 2, 2, 2, 3}{4, 4}{5, 5, 5, 5, 5}{6, 6}{7, 7}{8, 8, 8, 9} 3. 6箱但我们想要4，因此需要进行2次合并。
  • {1, 2, 2, 2, 3}{4, 4}{5, 5, 5, 5, 5}{6, 6, 7, 7}{8, 8, 8, 9} 3.第一合并
  • {1, 2, 2, 2, 3, 4, 4}{5, 5, 5, 5, 5}{6, 6, 7, 7}{8, 8, 8, 9} 3.第二合并

所以最小可实现最大为7

Answer 2

下面是一些psudocode会给你只是一个解决方案用最小箱量可能：

Sort the list of "Elements" with Element as a pair {Value, Quanity}. 

So for example {5,2,3,6,1,6} becomes an ordered set: 
Let S = {{1,1},{2,1},{3,1},{5,1},{6,2}} 

Let A = the largest quanity of any particular value in the set 
Let X = Items in List 
Let N = Number of bins 
Let MinNum = ceiling (X/N) 
if A > MinNum then Let MinNum = A 

Create an array BIN(1 to N+1) of pointers to linked lists of elements. 

For I from 1 to N 
    Remove as many elements from the front of S that are less than MinNum 
    and Add them to Bin(I) 
Next I 
Let Bin(I+1)=any remaining in S 

LOOP while Bin(I+1) not empty 
    Let MinNum = MinNum + 1 
    For I from 1 to N 
    Remove as many elements from the front of Bin(I+1) so that Bin(I) is less than MinNum 
    and Add them to Bin(I) 
    Next I 
END LOOP 

您的可能的最小纸盒尺寸为MinNum和BIN(1)至Bin(N)将包含值的分布。