3

I'm not exactly sure how to ask this, but I'll try to be as specific as possible. Imagine a tetris screen with only rectangles, of different shapes, falling to the bottom. I want to compute the maximum number of rectangles that I can fit one next to the other without any overlapping ones. I've named them lines in the title because I'm actually only interested in the length of the rectangle when computing, or the line parallel to the x axis that it's falling towards.

So basically I have a custom type with a start and end, both integers between 0 and 100. Say we have a list of these rectangles ranging from 1 to n. rectangle_n.start (unless it's the rectangle closest to the origin) has to be > rectangle_(n-1).end so that they will never overlap. I'm reading the rectangle coordinates (both are x axis coordinates) from a file with random numbers.

As an example: consider this list of rectangle type objects

rectangle_list {start, end} = {{1,2}, {3,5}, {4,7} {9,12}}

We can observe that the 3rd object has its start coordinate 4 < the previous rectangle's end coordinate which is 5. So in sorting this list, I would have to remove the 2nd or the 3rd object so that they don't overlap.

I'm not sure if there is a type for this kind of problem so I didn't know how else to name it. I'm interested in an algorithm that can be applied on a list of such objects and would sort them out accordingly.

I've tagged this with c++ because the code I'm writing is c++ but any language would do for the algorithm. initial state

final state

4

3 回答 3

5

您基本上是在解决以下问题。假设我们有的n区间。我们希望找到这些区间的最大子集，使得子集中的任何区间之间没有重叠。{[x_1,y_1),[x_2,y_2),...,[x_n,y_n)}x_1<=x_2<=...<=x_n

天真的解决方案是动态规划。它保证找到最佳解决方案。令f(i),0<=i<=n为最大子集的大小直到区间[x_i,y_i)。我们有方程（这是乳胶）：

f(i)=\max_{0<=j<i}{f(j)+d(i,j)}

其中d(i,j)=1当且仅当[x_i,y_i)且[x_j,y_j)没有重叠；否则d(i,j)取零。f(i)您可以从 开始迭代计算f(0)=0。f(n)给出最大子集的大小。要获得实际的子集，您需要保留一个单独的数组s(i)=\argmax_{0<=j<i}{f(j)+d(i,j)}。然后，您需要回溯以获取“路径”。

这是一种O(n^2)算法：您需要计算每个f(i)您f(i)需要i的测试次数。我认为应该有一个O(nlogn)算法，但我不太确定。

编辑：Lua 中的一个实现：

function find_max(list)
    local ret, f, b = {}, {}, {}
    f[0], b[0] = 0, 0
    table.sort(list, function(a,b) return a[1]<b[1] end)
    -- dynamic programming
    for i, x in ipairs(list) do 
        local max, max_j = 0, -1
        x = list[i]
        for j = 0, i - 1 do
            local e = j > 0 and list[j][2] or 0
            local score = e <= x[1] and 1 or 0
            if f[j] + score > max then
                max, max_j = f[j] + score, j
            end
        end
        f[i], b[i] = max, max_j
    end
    -- backtrack
    local max, max_i = 0, -1
    for i = 1, #list do
        if f[i] > max then -- don't use >= here
            max, max_i = f[i], i
        end
    end
    local i, ret = max_i, {}
    while true do
        table.insert(ret, list[i])
        i = b[i]
        if i == 0 then break end
    end
    return ret
end

local l = find_max({{1,2}, {4,7}, {3,5}, {8,11}, {9,12}})
for _, x in ipairs(l) do
    print(x[1], x[2])
end
于 2013-06-05T00:42:58.350 回答
3

这个问题的名称是装箱，它通常被认为是一个难题，但对于少量的箱可以很好地计算。

这是一个视频，解释了解决此问题的常用方法

编辑：通过难题，我的意思是必须使用某种蛮力。您将不得不评估很多解决方案并拒绝其中的大多数，因此通常您需要某种评估机制。您需要能够比较解决方案，例如“此解决方案包含 4 个面积为 15 的矩形”优于“此解决方案包含 3 个面积为 16 的矩形”。

于 2013-06-04T21:04:35.530 回答
2

我想不出捷径，因此您可能必须按大小降序枚举功率集并在第一场比赛时停止。

做到这一点的直接方法是枚举减小大小的组合。你可以在 C++11 中做这样的事情：

template <typename I>
std::set<Span> find_largest_non_overlapping_subset(I start, I finish) {
    std::set<Span> result;
    for (size_t n = std::distance(start, finish); n-- && result.empty();) {
        enumerate_combinations(start, finish, n, [&](I begin, I end) {
            if (!has_overlaps(begin, end)) {
                result.insert(begin, end);
                return false;
            }
            return true;
        });
    }
    return result;
}

的实现enumerate_combination留作练习。我假设你已经有了has_overlap.

于 2013-06-04T21:08:18.763 回答