仓库管理员的最优入库方案问题

mathe · 发表于 2014-11-5 08:46:58

找到一种机械构图方法，非常适合计算机来作。我们的目的是构造含n个黑点的黑白树，叶结点全是黑点，而且同色点不相邻。如图，n=1只有仅包含一个黑点的图1.1 然后对于每个图，如果去掉其所有叶结点，并且黑白互换，我们可以将其转化为一个低阶的图。于是，我们反过来可以通过将低阶图先黑白互换，然后每个叶结点都至少先添加一个黑点，此外如果黑点数目还不够，在各白点上继续添加适当数目的黑点即可。唯一的问题是有些结构会等价，需要删除之。如图，手工轻易构造到n=6

mathe · 发表于 2014-11-5 09:36:04

然后手工计算结果
f(2,1)=1
f(4,3)=2
f(5,4)=3, f(9,4)=4.
f(6,5)=6, f(7,5)=5, f(8,5)=4, f(11,5)=8, f(12,5)=6, f(16,5)=9
f(7,6)=11, f(13,6)=18, f(19,6)=21, f(25,6)=22。

然后手工计算结果f(2k+1,2)=1,f(3k+1,3)=2,f(3k+2,3)=1,f(5,4)=3,f(4k+1,4)=4,f(4k+3,4)=3.f(6,5)=6,f(5k+1,5)=9,f(7,5)=5,f(5k+2,5)=6,f(5k+3,5)=4,f(5k+4,5)=3,f(7,6)=10,f(13,6)=18,f(19,6)=20,f(6k+1,6)=21,f(6k+5,6)=5。当然上面的k是有范围限制的，也就是没有特殊值时才使用

mathe · 发表于 2014-11-5 09:50:35

提示: 该帖被管理员或版主屏蔽

hujunhua · 发表于 2014-11-5 10:27:51

提示: 该帖被管理员或版主屏蔽

mathe · 发表于 2014-11-5 21:42:10

对于任意一个m*n的解，其中m>n,其中n行，每行和为m,m列，每列和为n。我们在右边继续添加一个n*n对角线阵，对角线元素都是n,那么就得到一个(m+n)*n的解。而我上面分析给出对于充分大的m,解的形式都是这样的，也就是我们只要找那些不包含n*n阶对角阵的“基本解“即可。
进一步如果将解中所以只有一个非零元的列都删除，得到的矩阵可称为其“骨架“，显然通过骨架也非常容易变化回对应的解。而解的骨架正好对应图论表达形式中去掉所有叶接点的图。
如果将解树的所有叶结点都删除，得到的子树可称为其“骨架“，显然通过骨架也非常容易变化回对应的解。

mathe · 发表于 2014-11-6 08:17:58

首先我们可以计算骨架对应的图的数目，增长的不算太快，对应序列 http://oeis.org/A035053

mathe · 发表于 2014-11-6 11:01:19

Level 2

1

Level 3

1

2	2
1
	1

1	1
2
	2

Level 4

1

2	3
1
	1
1

3	3	3
1
	1
		1

1	1	1
3
	3
		3

2	3
2		3
	1
		1

2	1
2		1
	3
		3

Level 5

1

2	4
1
	1
1
1

3	3
1
	1
1
	1

1	1
2
	2
2
	2

3	4	4
1
	1
		1
1

1	3	3
2
	2
		2
2

2	4
2		4
	1
		1
1

1	2
1		2
	3
		3
3

3	3
2		4
	1
		1
	1

1	1
4		3
	2
		2
	2

4	4	4	4
1
	1
		1
			1

3	3	3	3
2
	2
		2
			2

2	2	2	2
3
	3
		3
			3

1	1	1	1
4
	4
		4
			4

3	4		4
2		4
	1
		1
			1

1	3		3
4		3
	2
		2
			2

4	2		2
1		2
	3
		3
			3

2	1		1
3		1
	4
		4
			4

3	3
2		4
	2		4
		1
			1

1	1
4		3
	4		3
		2
			2

4	4
1		2
	1		2
		3
			3

2	2
3		1
	3		1
		4
			4

Level 6

1

2	5
1
	1
1
1
1

3	4
1
	1
1
1
	1

3	5	5
1
	1
		1
1
1

4	4	5
1
	1
		1
1
	1

2	5
2		5
	1
		1
1
1

3	4
2		5
	1
		1
1
	1

4	3
2		5
	1
		1
	1
	1

3	4
3		4
	1
		1
	1
		1

4	5	5	5
1
	1
		1
			1
1

3	5		5
2		5
	1
		1
			1
1

4	4		5
2		5
	1
		1
			1
	1

3	5		5
3		4
	1
		1
			1
		1

2	5
2		5
2			5
	1
		1
			1

3	4
2		5
	2		5
		1
			1
1

3	4
3		4
	2		5
		1
			1
		1

5	5	5	5	5
1
	1
		1
			1
				1

1	1	1	1	1
5
	5
		5
			5
				5

4	5		5	5
2		5
	1
		1
			1
				1

2	1		1	1
4		1
	5
		5
			5
				5

3	5		5
3		5		5
	1
		1
			1
				1

3	1		1
3		1		1
	5
		5
			5
				5

4	4			5
2		5
	2		5
		1
			1
				1

2	2			1
4		1
	4		1
		5
			5
				5

3	4
3		5		5
	2		5
		1
			1
				1

3	2
3		1		1
	4		1
		5
			5
				5

3	4
3		4
	2		5
		2		5
			1
				1

3	2
3		2
	4		1
		4		1
			5
				5

Level 7

1

2	6
1
	1
1
1
1
1

3	5
1
	1
1
1
1
	1

4	4
1
	1
1
1
	1
	1

1	1
2
	2
2
2
	2
	2

3	6	6
1
	1
		1
1
1
1

4	5	6
1
	1
		1
1
1
	1

1	3	5
2
	2
		2
2
2
	2

5	5	5
1
	1
		1
1
	1
		1

3	3	3
2
	2
		2
2
	2
		2

1	1	1
3
	3
		3
3
	3
		3

2	6
2		6
	1
		1
1
1
1

3	5
2		6
	1
		1
1
1
	1

4	4
2		6
	1
		1
1
	1
	1

1	1
4		5
	2
		2
2
	2
	2

3	5
3		5
	1
		1
1
	1
		1

2	1
2		1
	3
		3
3
	3
		3

5	3
2		6
	1
		1
	1
	1
	1

4	4
3		5
	1
		1
	1
	1
		1

1	1
6		3
	2
		2
	2
	2
		2

4	6	6	6
1
	1
		1
			1
1
1

1	5	5	5
2
	2
		2
			2
2
2

5	5	6	6
1
	1
		1
			1
1
	1

3	3	5	5
2
	2
		2
			2
2
	2

1	1	4	4
3
	3
		3
			3
3
	3

3	6		6
2		6
	1
		1
			1
1
1

4	5		6
2		6
	1
		1
			1
1
	1

1	3		5
4		5
	2
		2
			2
2
	2

3	6		6
3		5
	1
		1
			1
1
		1

2	4		4
2		1
	3
		3
			3
3
		3

5	4		6
2		6
	1
		1
			1
	1
	1

3	1		5
4		5
	2
		2
			2
	2
	2

4	5		6
3		5
	1
		1
			1
	1
		1

1	3		5
6		3
	2
		2
			2
	2
		2

5	1		4
2		1
	3
		3
			3
	3
		3

5	5		5
2		6
	1
		1
			1
	1
			1

3	3		3
4		5
	2
		2
			2
	2
			2

1	1		1
6		4
	3
		3
			3
	3
			3

3	6		6
4		4
	1
		1
			1
		1
		1

6	5		5
1		1
	2
		2
			2
		2
		2

2	6
2		6
2			6
	1
		1
			1
1

1	3
1		3
1			3
	4
		4
			4
4

3	5
2		6
2			6
	1
		1
			1
	1

3	5
2		6
	2		6
		1
			1
1
1

4	4
2		6
	2		6
		1
			1
1
	1

1	1
4		5
	4		5
		2
			2
2
	2

2	2
1		3
	1		3
		4
			4
4
	4

3	5
3		5
	2		6
		1
			1
1
		1

2	1
2		1
	6		4
		3
			3
3
		3

4	4
2		6
	3		5
		1
			1
1
			1

1	1
4		5
	6		3
		2
			2
2
			2

3	5
4		4
	2		6
		1
			1
		1
		1

6	3
1		1
	4		5
		2
			2
		2
		2

4	4
3		5
	3		5
		1
			1
		1
			1

1	1
6		3
	6		3
		2
			2
		2
			2

5	5
2		1
	2		1
		3
			3
		3
			3

5	6	6	6	6
1
	1
		1
			1
				1
1

3	5	5	5	5
2
	2
		2
			2
				2
2

1	4	4	4	4
3
	3
		3
			3
				3
3

4	6		6	6
2		6
	1
		1
			1
				1
1

1	5		5	5
4		5
	2
		2
			2
				2
2

2	3		3	3
1		3
	4
		4
			4
				4
4

5	5		6	6
2		6
	1
		1
			1
				1
	1

3	3		5	5
4		5
	2
		2
			2
				2
	2

1	1		4	4
6		4
	3
		3
			3
				3
	3

4	6		6	6
3		5
	1
		1
			1
				1
		1

1	5		5	5
6		3
	2
		2
			2
				2
		2

5	4		4	4
2		1
	3
		3
			3
				3
		3

3	6		6
3		6		6
	1
		1
			1
				1
1

2	4		4
2		4		4
	3
		3
			3
				3
3

1	2		2
1		2		2
	5
		5
			5
				5
5

4	5		6
3		6		6
	1
		1
			1
				1
	1

1	3		5
6		5		5
	2
		2
			2
				2
	2

5	1		4
2		4		4
	3
		3
			3
				3
	3

3	6			6
2		6
2			6
	1
		1
			1
				1

5	3			3
1		3
1			3
	4
		4
			4
				4

1	2			2
3		2
3			2
	5
		5
			5
				5

4	5			6
2		6
	2		6
		1
			1
				1
1

1	3			5
4		5
	4		5
		2
			2
				2
2

2	6			3
1		3
	1		3
		4
			4
				4
4

4	5			6
3		5
	2		6
		1
			1
				1
		1

1	3			5
6		3
	4		5
		2
			2
				2
		2

5	1			4
2		1
	6		4
		3
			3
				3
		3

5	5			5
2		6
	2		6
		1
			1
				1
				1

3	3			3
4		5
	4		5
		2
			2
				2
				2

1	1			1
6		4
	6		4
		3
			3
				3
				3

3	5
3		6		6
	2		6
		1
			1
				1
1

2	1
2		4		4
	6		4
		3
			3
				3
3

1	4
1		2		2
	3		2
		5
			5
				5
5

4	4
3		6		6
	2		6
		1
			1
				1
	1

1	1
6		5		5
	4		5
		2
			2
				2
	2

2	2
5		3		3
	1		3
		4
			4
				4
	4

3	5
4		5		6
	2		6
		1
			1
				1
		1

6	3
1		3		5
	4		5
		2
			2
				2
		2

2	1
5		1		4
	6		4
		3
			3
				3
		3

4	4
3		6		6
	3		5
		1
			1
				1
			1

1	1
6		5		5
	6		3
		2
			2
				2
			2

5	5
2		4		4
	2		1
		3
			3
				3
			3

3	5
2		6
	2		6
2				6
		1
			1
				1

5	6
1		3
	1		3
1				3
		4
			4
				4

1	4
3		2
	3		2
3				2
		5
			5
				5

[table=3,skyblue][t]

wayne · 发表于 2014-11-6 11:12:32

mathe 在27# 贴的这么壮观的表格是C++程序生成的吧？聪明！

mathe · 发表于 2014-11-6 12:52:49

(8,13)阶问题的解也可以全部算出了，应该36个

1	1			3	8
2		3				8
	2		3				8
		5						8
			5						8
				5						8
5											8
	5											8

2	3				8
2		3				8
2			3				8
2				3				8
	5								8
		5								8
			5								8
				5								8

4	1				8
2		3				8
	2		3				8
2				3				8
		5							8
			5							8
				5							8
	5											8

4	1				8
4		1				8
	2		3				8
		2		3				8
			5						8
				5						8
	5										8
		5										8

1	3		3	3	3
2		3				8
	5						8
		5						8
			5						8
				5						8
					5						8
5												8

4	3			3	3
2		3				8
2			3				8
	5							8
		5							8
			5							8
				5							8
					5							8

1	6			3	3
2		3				8
	2		3				8
		5						8
			5						8
				5						8
					5						8
5												8

1	1			3		8
7		3			3
	2		3				8
		5						8
			5						8
				5						8
					5						8
	5											8

4	1					8
4		3		3	3
	2		3				8
		5						8
			5						8
				5						8
					5						8
	5											8

4	6				3
2		3				8
	2		3				8
2				3				8
		5							8
			5							8
				5							8
					5							8

4	1					8
2		3					8
	7		3		3
2				3				8
		5							8
			5							8
				5							8
					5							8

1	6	6
2			3			8
	2			3			8
		2			3			8
			5						8
				5						8
					5						8
5												8

1	1				3	8
7		6
	2		3				8
		2		3				8
			5						8
				5						8
					5						8
	5											8

4	6				3
4		1				8
	2		3				8
		2		3				8
			5						8
				5						8
					5						8
		5										8

4	1					8
4		1					8
	7		3		3
		2		3				8
			5						8
				5						8
					5						8
		5										8

1	4					8
7		6
	2		3				8
		2		3				8
	2				3				8
			5							8
				5							8
					5							8

4	1					8
4		1					8
	7		6
		2		3				8
			2		3				8
				5						8
					5						8
		5										8

1	3		3	3	3
7		3				3
	5						8
		5						8
			5						8
				5						8
					5						8
						5						8

4	3		3	3
4		3			3	3
	5						8
		5						8
			5						8
				5						8
					5						8
						5						8

1	6			3	3
7		3				3
	2		3				8
		5						8
			5						8
				5						8
					5						8
						5						8

4	6			3
4		3			3	3
	2		3				8
		5						8
			5						8
				5						8
					5						8
						5						8

1	1			3			8
7		3			3
	7		3			3
		5						8
			5						8
				5						8
					5						8
						5						8

7	6
1		3		3	3	3
	2		3				8
		5						8
			5						8
				5						8
					5						8
						5						8

4	1						8
4		3		3	3
	7		3			3
		5						8
			5						8
				5						8
					5						8
						5						8

1	6	6
7			3			3
	2			3			8
		2			3			8
			5						8
				5						8
					5						8
						5						8

1	6				3	3
7		6
	2		3				8
		2		3				8
			5						8
				5						8
					5						8
						5						8

4	6				3
4		6				3
	2		3				8
		2		3				8
			5						8
				5						8
					5						8
						5						8

1	1				3		8
7		6
	7		3			3
		2		3				8
			5						8
				5						8
					5						8
						5						8

4	6				3
4		1					8
	2		3					8
		7		3		3
			5						8
				5						8
					5						8
						5						8

1	4						8
7		6
	4		3		3	3
		2		3				8
			5						8
				5						8
					5						8
						5						8

4	1						8
4		1						8
	7		3		3
		7		3		3
			5						8
				5						8
					5						8
						5						8

1	6		6
7		6
	2			3			8
		2			3			8
			2			3			8
				5						8
					5						8
						5						8

1	1					3	8
7		6
	7		6
		2		3				8
			2		3				8
				5						8
					5						8
						5						8

4	1						8
4		6				3
	7		6
		2		3				8
			2		3				8
				5						8
					5						8
						5						8

4	1						8
4		1						8
	7		6
		7		3		3
			2		3				8
				5						8
					5						8
						5						8

4	1						8
4		1						8
	7		6
		7		6
			2		3				8
				2		3				8
					5						8
						5						8

Total 36 found

mathe · 发表于 2014-11-6 13:43:50

前面我们两手工得出俩结果好像走了俩极端，分别是第一个和最后一个解

账号		自动登录	找回密码
密码			欢迎注册

[原创] 仓库管理员的最优入库方案问题

点评