我必须写一个算法分配毗连座椅在座椅map.For例如：在体育场分配席位。座位图可以被看作是N行和M列的二维数组。系统必须对所做在一起预订分配连续的席位。由于没有座位图是psented用户$ P $，系统应自动分配对应于每个购买可用座位。除了这一点，应该以这样的方式，使得所述的孔/在席间隙被最小化做到这一点。

I have to write an algorithm for Assigning Contiguous seats in a seat map.For example: allocating seats in a stadium. The seat map can be viewed as a 2d array of N rows and M columns. The system must assign contiguous seats for bookings that are made together. Since no seat map is presented to the user, the system should automatically assign the available seats corresponding to each purchase. In addition to this, it should do this in such a fashion such that the holes/gaps in the seats are minimized.

推荐答案

找到一个完美的解决方案是 NP -hard 。看相当于语言的问题： L = {（（X1，X2，...，XK），N，M）} 其中，xi是共同订好机票的数量，而n ，m为球场的大小。

Finding a perfect solution is NP-hard. Look at the equivalent language problem: L={((x1,x2,...,xk),n,m)} where xi are the number of co-booked tickets, and n,m are the stadium sizes.

我们将展示分区＆LT; =（P）L，因此这个问题是NP -hard，并且对于它没有已知的多项式溶液

We will show Partition <=(P) L, and thus this problem is NP-Hard, and there is no known polynomial solution for it.

证明 让 S =（X1，X2，...，XK）是输入一个分区的问题，并让和= X1 + ... + XK 请看下面的降低：

Proof let S=(x1,x2,..,xk) be the input for a partition problem, and let sum=x1+...+xk Look at the following reduction:

Input: S=(x1,...,xk)
Output:((x1,...,xk),sum/2,2)

正确性： 如果S有一个分区，让它成为 S1 =（x_i1，x_i2，...，x_it），然后通过分区定义， x_i1 +。 .. + x_it = SUM / 2 ，因此，我们可以插入 x_i1，...，x_it 排在第一位，其余的第二行，等等（（X1，...，XK），总和/ 2,2）为L 如果（（X1，...，XK），总和/ 2,2）是L，则根据定义有T个订单，使得 x_i1，x_i2，...，x_it 形成一个完美的第一线，因而 x_i1 + x_i2 + ... + x_it = SUM / 2 ，因此它是一个有效的分区和S是在分区问题

Correctness: If S has a partition, let it be S1=(x_i1,x_i2,...,x_it), then by definition of partition, x_i1+...+x_it=sum/2, and thus we can insert x_i1,..,x_it in the first row, and the rest in the second row, and so ((x1,...,xk),sum/2,2) is in L If ((x1,...,xk),sum/2,2) is in L, then by definition there are t bookings such that x_i1,x_i2,...,x_it form a perfect first line, and thus x_i1+x_i2+...+x_it=sum/2, and thus it is a valid partition and S is in Partition problem

结论： 因为L是NP难，和你所寻求的问题是这种语言的优化问题，对于它没有已知的多项式的解决方案。对于一个确切的解决方案，您可以使用回溯【检查所有的可能性，并选择最佳]，但它将花费大量的时间，也可以sattle一个启发式的解决方案，如贪婪，但它不会被优化

Conclusion: Since L is NP-Hard, and the problem you seek is the optimization problem for this language, there is no known polynomial solution for it. For an exact solution you can use backtracking [check all possibilities, and choose the best], but it will take a lot of time, or you can sattle for a heuristic solution, such as greedy, but it will not be optimized.

编辑：回溯解[伪code]：

Backtracking solution [pseudocode]:

solve(X,n,m):
   global bestVal <- infinity
   global bestSol <- null
   solve(X,new Solution(n,m))
solve(X,solution):
   if (X is empty):
       gaps <- solution.numGaps()
       if (gaps < bestVal):
            bestVal <- gaps
            bestSol <- solution
       return
   temp <- X.first
   X.removeFirst()
   for i from 0 to m:
       solution.addToLine(i,temp)
       solve(X,solution)
       solution.removeFromLine(i,temp)
   X.addFirst(temp)

假设解决方案是一个实现类，并为非法的解决方案[即太多的人在一排] numGaps（）==无限

Assuming Solution is an implemented class, and for an illegal solution [i.e. too many people in one row] numGaps() == infinity