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

hujunhua

我在8、9、10#@mathe的帖中补充了内容，可能会对后面产生影响，后面要有所简化了，我会跟进编辑的。
mathe看一看，原谅一下我这先生后准。

mathe

9#后面部分的结论是错误的。只有一个数的列超过n列时，不一定必然可以凑出对角阵的。其他部分都修订的很好

mathe

hujunhua 发表于 2014-11-6 17:34
发现9楼补充的证明尾巴也有问题。结果就是“每一个树G（E,m,n)都可对应一个非负最优矩阵“不成立。不能保证 ...

不一定对于所有的m都有解，即使将m替换成更加大的m+kn以后会有不一定有解。
实际上另外一种方法可以在求边的权重时，先全部进行模n运算。我们知道在模n下有唯一解。（需要注意这时连叶结点的边的权重n总是变成0，所以可以不考虑）。
1. 对于每个白点，如果和它关联的各边权重和不是n(必然是n的倍数），那么也不是合法的解，
2. 如果对于某个黑点，其各边权重和大于m,也不合法（但是可以是(m+h*n,n)问题的解）
但是计算结果发现好像对于每个骨架图（同m无关），总会存在m使得有对应的图解。但是不是对所有的m都有解，这个结论也没有证明过.
现在回家了，总算可以上载附件了，把代码作为附件给出

mathe

附件中程序对等价的树处理的不够好，这部分浪费的时间比较多，可以改善。
比如开始只有一个点的树，我们把这个点记为0，如果在0点添加五个节点，我们分别记为0.1,0.2,0.3,0.4,0.5,得到的新的6个点的对称关系可以通过{0.1,0.2,0.3,0.4,0.5}五个点的置换表示。
然后如果0.1,0.2,0.3再添加一个点，0.4,0.5各添加两个点，这些点位0.1.1,0.2.1,0.3.1,0.4.1,0.4.2,0.5.1,0.5.2,那么新的对称关系可以通过{0.1,0.2,0.3},{0.4,0.5},{0.4.1,0.4.2},{0.5.1,0.5.2}表示

wayne

mathe 写代码的功力好深厚，就为了这么一个题目，洋洋洒洒就是700行（代码格式化之后）！

mathe

hujunhua的条件没有问题。 我现在好歹也是个职业程序员了。写个代码，算法前面都讨论过了，又不需要注释，不考虑可维护性，自然很快