algorithm - 在固定行数中拆分不同宽度的项目

Question

基本上，假设我有 5 个具有以下宽度的项目（高度对此并不重要，所以我们假设它们的高度均为 50 像素）：

50
100
100
100
50

而且我想尽可能地将它们分成2个不同的行（它必须按那个顺序）。我如何计算行的最小宽度来做到这一点？

注意：这并不像将所有宽度相加并除以行数那么简单，如果您使用上面的示例进行操作，则项目将不适合，因为宽度总和 (400) 除以行数行 (2) 为 200 (400 / 2 = 200)，在这种情况下，第五项将不适合任何行。

如果使用我刚才提到的方法，这是另一个不起作用的示例：

100
50
100
50
50
50

在这种情况下，最后两项（5 和 6）将需要一个额外的行。

AC# 示例会非常好，因为它是我用来执行此操作的语言 =)。

谢谢！

score 3 · Accepted Answer

假设您正在尝试将N宽度项目放入宽度{W[i]}行R中C；你R是固定的，你C是未知的。

首先，让我们做一些重要的观察：

给定 a C，很容易检查选择该特定项是否C会使您的排列精确到R行：您可以通过逐个检查项目、计算运行总数并C用作截止点来做到这一点。
的最小值C是最小的W[i]；最大值是W[i]s的总和
增加C可以使所需的行数C减少，但不能增加；因此，函数RequiredRows(C, W[0..N])是单调的。

这些观察导致了一个简单的算法：运行最小的二分搜索，C这样 RequiredRows(C, W[0..N]) == R通过在二分搜索的每一步运行基于运行总数的检查器。

这是 C# 中的骨架实现：

private static int RequiredRows(int C, int[] data) {
    var res = 1;
    var total = 0;
    foreach ( var w in data) {
        if (total+w <= C) {
            total += w;
        } else {
            res++;
            total = w;
        }
    }
    return res;
}
public static void Main() {
    var data = new[] {50,100,100,100,50};
    var R = 2;
    var start = data.Max();
    var end = data.Sum();
    while (start+1 < end) {
        var mid = start+((end-start)/2);
        if (RequiredRows(mid, data) > R) {
            start = mid;
        } else {
            end = mid;
        }
    }
    Console.WriteLine(end);
}

score 1 · Accepted Answer

如果顺序是固定的并且正好有两行，这是一个相当简单的问题。将您的宽度数组转换为累积数组。对于第一个示例，它将是：

50
150
250
350
400

第二个是：

100
150
250
300
350
400

然后只需搜索最接近最后一个条目一半的条目，并将列表在该条目之后一分为二。任意解决关系（因此，在任一示例中的第 2 项或第 3 项之后）。最小行宽度是条目累积宽度的最大值或与总宽度（最后一个累积条目）之间的差异。

score 0 · Accepted Answer

考虑需要两行的情况。您可以只测试列表中所有可能的分割点（索引），看看哪一个产生最好的结果（最小化最大行宽）。

对于超过两行，只需使用递归继续拆分“右半部分”，如下面的代码示例所示。（Python）

def split(sizes, count):
    # base case: one row, just return it
    if count == 1:
        return [sizes]
    best_score = None
    best_result = None
    # for each possible split point (don't allow empty rows)
    for i in range(1, len(sizes)):
        # the first row is the columns up to the split point
        left = [sizes[:i]]
        # recurse to process the remaining rows
        right = split(sizes[i:], count - 1)
        if right is None:
            # failed to split count - 1 times, ignore
            continue
        rows = left + right
        # minimize the maximum row width
        score = max(sum(row) for row in rows)
        if best_score is None or score < best_score:
            best_score = score
            best_result = rows
    return best_result

if __name__ == '__main__':
    sizes = [100, 50, 100, 50, 50, 50]
    print split(sizes, 2)
    print split(sizes, 3)

输出：

[[100, 50], [100, 50, 50, 50]] # 2 rows
[[100], [50, 100], [50, 50, 50]] # 3 rows

algorithm - 在固定行数中拆分不同宽度的项目

3 回答 3

Related

Reference