有n（n < 1000）个朋友组，组的大小由数组A[]（2 <= A[i] < 1000）表示。桌子的存在使得它们一次可以容纳r(r>2)人。每个人的座位最少需要多少张桌子，但每个人的座位上都应该有其他人坐在他/她的座位上。
我想的方法是把每一组分成两三个小组，并试图解决这个问题，但是有很多方法可以把一个数字分成两三个小组，并不是所有的方法都是最佳的。
最佳答案
混合整数规划模型算数吗？
关于这一提法的一些说明：
我用随机数据组成小组。
x（i，j）是i组坐在j桌旁的人数。
x（i，j）是一个半整数变量，即：它是一个值为零或介于lo和up之间的整数变量。并非所有的MIP解算器都提供半连续和半整数变量，但它可能会很方便在这里，我用它来强制要求来自同一组的至少两个人坐在一张桌子旁。如果解算器不提供这些类型的变量，我们也可以使用附加的二进制变量来构造此构造。
y（j）是指示是否使用表的二进制变量（0或1）。
容量方程有点聪明：如果不使用表（y（j）=0），它的容量将减少到零。
选项optcr=0表示我们要求解到最优性。对于大的，困难的问题，我们可能不想说5%。
顺序方程确保我们从表1开始填写表格。这也降低了问题的对称性，并可能加快解决时间。
上面的模型（包含200个组和200个可能使用的表）生成了一个包含600个方程（行）和40k个变量（列）的mip问题。有37k个整数变量。使用一个好的mip解算器，我们可以在不到一分钟的时间内找到经验证的最佳解决方案（使用150个表）。
注意，这当然不是背包问题（正如在另一个答案中所建议的——背包问题只有一个约束），但它类似于装箱问题。