同学聚会

mathe

我没有注意到是4张桌子,那还要重新考虑一下,这个规模感觉应该比一张桌子的小

mathe

这样就先考虑一张桌子的不同情况,复杂度是我上面提到方程k=10时的情况,这个应该很小.先分析好这个问题,然后就可以组合出其它情况了

northwolves

看来规模有点大,可以试着用动态规划解决,问题规模同下面不定方程的非负整数解数目相关
$2*x_1+x_2+x_3+2*y_1+y_2+y_3=k$
其中要求$x_1+x_2
mathe 发表于 2010-1-20 07:44

针对$2*x1+x2+x3+2*y1+y2+y3=10$的1059组非负整数解,各自对应着多种落座方法.
假设4桌的落座方案分别为:
${:(x11,x21,x31,y11,y21,y31),(x12,x22,x32,y12,y22,y32),(x13,x23,x33,y13,y23,y33),(x14,x24.x34.y14,y24,y34):}$
则有:
${:(x11+x12+x13+x14+x21+x22+x23+x24=12),(y11+y12+y13+y14+y21+y22+y23+y24=8),(x31+x32+x33+x34+y11+y12+y13+y14=8),(x11+x12+x13+x14+y31+y32+y33+y34=12):}$

northwolves

是否可以考虑用数组n[x1,x2,x3,y1,y2,y3]记录每桌的某种落座方案种数?

northwolves

是否可以考虑用数组n[x1,x2,x3,y1,y2,y3]记录每桌的某种落座方案种数?
northwolves 发表于 2010-1-20 13:59

即使这个感觉也不是很好计算

mathe

这个还是相对比较好做的,可以事先指定x1,x2,...等等对应的人,那么落座方式枚举出来并不难.
然后此后可以计算前两桌坐的人的组合情况,相当于对应方程中k=20的情况,而这个枚举数可以直接通过一桌的情况来计算;同样余下两桌的数目也可以计算起来,然后相乘;最后还需要乘上使用不同排列方案的数目

mathe

针对$2*x1+x2+x3+2*y1+y2+y3=10$的1059组非负整数解,各自对应着多种落座方法.
假设4桌的落座方案分别为:
${x11,x21,x31,y11,y21,y31),(x12,x22,x32,y12,y22,y32),(x13,x23,x33,y13,y23,y33),(x14,x24.x34.y ...
northwolves 发表于 2010-1-20 13:43

我试了一下，只有1056个解，而不是1059个解。
第一步的任务就是给这1056个解都求出计数（假设每个中人的数目都已知）

mathe

进一步过滤一下，发现方程只有1024个解，其中，只有764组解有合法的入座方式。
由于问题规模不大，就不用使用动态规划，直接穷举把每个解的入座数目给穷举出来

mathe

其中数目只考虑10个人的相对位置，如果认为每个人平移一个位置得到的结果是不同的，还需要在最后结果再乘上10，但是对于这里，就没有必要了。

mathe

下一步，只需要将724个不同组合中每次选择4个合并在一起，再次检查会不会出现冲突。直接穷举最多${724^4}/24$，实际上应该可以再次相互裁剪掉一些。
然后最后，对于每个方案，由于我们应该区分所有的人，而不仅仅看他们的性别和配偶关系；于是这个对每个前面找到的方案，还需要乘上一个组合数。