砝码题
有一架天平和101个总重量为200克的砝码，砝码的重量都是整数克，但具体数值不详。请设计一种方法，把所有砝码分置天平的两端而使天平平衡，并说明该方法的可行性。 这个可以请 @Mathematica坛友来穷举。 从重到轻贪心法放置即可
i)最重的砝码先放任意一侧
ii)反复将当前最重的砝码放置天平总重量较轻的一侧，直到所有砝码放置完毕。
以下说明这种方法必然最后会导致天平两侧平衡。
由抽屉原理可知至少有 2 个 1 克的砝码。
所以假如最后不平衡（两侧至少相差 2 克），那么说明
最后在天平左侧连续放置了 u 个共 a 克砝码，但是左侧比右侧仍然轻至少 2 克以上
假设此前在天平右侧最后一次放置了 1 个 b 克的砝码,则
$a>=u,b>=a+2>=u+2$
即最后$u$个砝码至少$u$克, 而之前$101-u$个砝码都不轻于$u+2$克，故
$u+(101-u)(u+2)<=200$ → $u(u-100)>=2$ →$ u<0$ 或 $u>=101$
这不可能。所以天平两边必然会平衡。 没注意题目中有砝码重量不详，如果这样，我们认为就可以是先比较所有砝码之间轻重关系即可。于是每次可以只比较两个砝码重量，给它们排好序。接下去就可以用贪心法了 所谓不详，我理解为在制定方案前，丢番图方程\的解不明，具体的重量配置可能是方程解集中的任何一个。所以我们制定的方案应对解集中任意一个特定的解都可行。当具体实施时，我们面临的是一个特定解，各重量是已知的。
2楼的贪心算法就是一个这样的方案。事实上，该方案并不需要具体的重量值，只需要按重量的排序即可。
页:
[1]