문제 설명
가장 효율적인 좌석 배치 (Most efficient seating arrangement)
n(n <1000)개의 친구 그룹이 있으며 그룹의 크기는 A[] (2 <= A[i] <1000). 테이블은 한 번에 r(r>2)명을 수용할 수 있도록 제공됩니다. 모든 사람이 앉는 데 필요한 최소 테이블 수는 얼마입니까? 모든 사람이 자신의 테이블에 앉을 수 있는 그룹의 다른 사람이 있어야 한다는 제약 조건이 있습니다.
제가 생각한 접근 방식은 다음과 같습니다. 모든 그룹을 2와 3의 크기로 나누고 이 문제를 해결하려고 시도하지만 숫자 n을 2와 3의 그룹으로 나누는 많은 방법이 있으며 모두가 최적이 아닐 수도 있습니다.
참조 솔루션
방법 1:
Does a Mixed Integer Programming model count?
Some notes on this formulation:
- I used random data to form the groups.
- x(i,j) is the number of people of group i sitting at table j.
- x(i,j) is a semi‑integer variable, that is: it is an integer variable with values zero or between LO and UP. Not all MIP solvers offer semi‑continuous and semi‑integer variables but it may come handy. Here I use it to enforce that at least 2 persons from the same group need to sit at a table. If a solver does not offer these type of variables, we can formulate this construct using additional binary variables as well.
- y(j) is a binary variable (0 or 1) indicating if a table is used.
- the capacity equation is somewhat smart: if a table is not used (y(j)=0) its capacity is reduced to zero.
- the option optcr=0 indicates we want to solve to optimality. For large, difficult problems we may want to stop say at 5%.
- the order equation makes sure we start filling tables from table 1. This also reduces the symmetry of the problem and may speed up solution times.
- the above model (with 200 groups and 200 potentially used tables) generates a MIP problem with 600 equations (rows) and 40k variables (columns). There are 37k integer variables. With a good MIP solver we find the proven optimal solution (with 150 tables used) in less than a minute.
- Notice this is certainly not a knapsack problem (as suggested in another answer ‑‑ a knapsack problem has just one constraint) but it resembles a bin‑packing problem.
방법 2:
It is same problem as knapsack problem which is NP complete (see https://en.wikipedia.org/wiki/Bin_packing_problem ). So finding optimal solution is pretty hard.
A heuristic that works most of the time:
Sort the groups according decreasing size.
For each group put it in the table that has least amount of space, but still can accommodate this group.
방법 3:
Your approach is workable. If a solution exists for a given number of tables, then a solution exists where you've split every group into some number of twos and some number of threes. First, split a three off of every group of odd size. You're left with a bunch of groups of even size. Next, split twos off of every group whose size isn't divisible by six. And forget that it's one bigger group; split it into a bunch of groups of six.
At this point, you have split all of your groups into some number of twos, some number of threes, and some number of sixes. Give each table of odd size one three, splitting sixes as necessary; now all tables have even size. All remaining sixes can now be split into twos and seated arbitrarily.
(by SHB、Erwin Kalvelagen、ElKamina、tmyklebu)