称砝码问题的一般解

砝码称重问题怎么用贪心算法解决~

现有1g、2g、3g、5g、10g、20g的砝码各若干枚，问用这些砝码可以称出多少种不同的重量。（设砝码的总重量不超过1000克，且砝码只能放在天平的一端）
输入方式：a1 a2 a3 a4 a5 a6
(表示1g砝码有a1个，2g砝码有a2个，......20g砝码有a6个)
输出方式:Total=N
(N表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况)
如:输入:1 1 0 0 0 0
输出:Total=3 表示可以称出1g,2g,3g三种不同的重量。

#include

int main( )
{
int a[ 6 ], m[ 6 ], total = 0, i, j, k, f[ 1001 ];
for ( i = 0; i <= 1000; i++ )
f[ i ] = 0;
f[ 0 ] = 1;
m[ 0 ] = 1; m[ 1 ] = 2; m[ 2 ] = 3; m[ 3 ] = 5; m[ 4 ] = 10; m[ 5 ] = 20;
for ( i = 0; i < 6; i++ )
scanf("%d", &a[ i ]);
for ( i = 0; i < 6; i++ )
{
for ( j = 0; j < a[ i ]; j++ )
{
for ( k = 1000; k >= m[ i ]; k-- )
if ( f[ k - m[ i ] ] && !f[ k ] )
{
f[ k ] = 1;
total++;
}
}
}
printf("Total=%d
", total);
return 0;
}

#include
using namespace std;
int i,a1,a2,a3,a5,a10,a20,b1,b2,b3,b5,b10,b20,h=0;
bool b[1001];
int main()
{
cin>>a1>>a2>>a3>>a5>>a10>>a20;
for (i=0;i<1001;++i) b[i]=false;
for (b1=0;b1<=a1;++b1)
for (b2=0;b2<=a2;++b2)
for (b3=0;b3<=a3;++b3)
for (b5=0;b5<=a5;++b5)
for (b10=0;b10<=a10;++b10)
for (b20=0;b20<=a20;++b20)
b[b1+b2*2+b3*3+b5*5+b10*10+b20*20]=true;
for (i=1;i<1001;++i) if (b[i]==true) ++h;
cout<<h;
return 0;
}

真正的答案在这里，让小弟深入浅出的从头讲起，虽然有点长，但保证各位看完之後彻底理解．

　命题A：有3^m个物件，其中1个是次品且知道次品比较轻，这样可以透过m次测量找出次品．
　证明：每次测量都有三种结果，所以测量之後都可以将范围缩小成为原先的1/3．

　命题B：有3^m个物件，其中1个是次品．此外，对於每一个物件，我们知道＂如果它是次品的话，那麼次品是较轻或是较重＂，这样我们仍然可以透过m次测量找出次品．
　举例：现有3^m个物件，其中1个是次品．假设我们知道，如果1号是次品，那麼次品比较轻；如果2号是次品，那麼次品比较重；如果3号是次品，那麼次品比较重．．．如果3^m号是次品，那麼次品比较轻－－这样的话，我们仍可以透过m次测量找出次品．

　证明：其实命题B与命题A同构．命题A比较无脑，每次测量之後，我们都可以很简单地确定次品是在＂天平左边＂、＂天平右边＂或是＂秤外＂．相形之下命题B比较复杂，每次测量之後，我们仍然可以将范围缩小成为1/3，这不过这1/3未必像命题A那样通通在秤的某一边，而是＂秤左边的第2号或第4号比较轻＂或者＂秤右边的第5号比较重＂这类的答案．但无论如何，每次测量之後我们还是可以把范围缩小成为1/3，所以命题B与命题A所需要的测量次数是相同的．

　命题C：有3^m个物件，其中1个是次品，但不知是轻是重，同时额外还有无数个标准品可供你使用．假设先前有人将这3^m个物件平均分放到天平的两侧（当然要添加一个正品才能凑成偶数），并且测量出结果了（肯定不是平衡的）．此後，你只要再秤一次，就可以把问题改写成为＂3^(m-1)个物件的命题B＂．换句话说，你只要再秤一次，不但可以把范围缩小成为1/3，还可以知道＂如果某一个物件是次品的话，那麼它将是轻还是重＂．

　证明：在第二次测量之前，将所有3^m个物件分为三类，每类3^(m-1)个：
　　　　第一类：保持不动：原先在天平左边的就留在左边，原先在天平右边的就留在右边．
　　　　第二类：左右换位：原先在天平左边的就换到右边，原先在天平右边的就换到左边．
　　　　第三类：彻底消失：通通拿下来，放到旁边．
　　　　如果左右物件数量不同的话，用额外的标准品补上．
　这样的话，如果第二秤与第一秤结果相同，那麼次品就在＂保持不动＂的那一组；如果前两秤结果相反，那麼次品就在＂左右换位＂的那一组；如果第二秤左右平衡了，那麼问题就在＂彻底消失＂的那一组；所以范围可以缩小成为1/3．
　又，依据前两秤的结果，我们不难得知如果某一个物品是次品的话，那麼它是较轻还是较重．这样就完全等价於命题B了．
　换句话说，命题C告诉我们：＂只需要秤两次，就可以将原问题的范围缩小成为1/3，并简化成为命题B＂．

好，现在来解本题．很明显的，在第一秤时，我们一定是将p个物件分放到天平左右，并留下q个物件在外面；其中p为偶数，q为非负整数．

令f(n)代表＂在秤n次的情况之下，所能够处理的物件数量上限＂，那麼我们可以列出下式：
　－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
　f(n) = 如果第一秤的p个物件左右不平衡，我们可以使用命题C解决这p个物件
　 　 　＋
　 　如果第一秤的p个物件平衡了，则在少了一秤的情况下，我们必须能够解决q个物件
　－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

先看第一条，我们知道使用命题C要先秤2次，然后才能将3^m个物件缩小成为3^(m-1)个物件的命题B．又命题B告诉我们3^(m-1)个物件需要再秤m-1次才能得到最终答案，因此从头到尾一共要秤m+1次才能解决3^m个物件，故上面公式可以改写为：
　－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
　f(m+1) = 第一秤天平左右两端一共有 3^m 个物件，若不平衡必能用命题C解决
　 　 　 　＋
　　 　如果第一秤平衡了，则在少了一秤的情况下，我们必须能够解决剩下的q个物件
　－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

其实上式是错的，因为 3^m 是个奇数，我们没有办法将奇数平均分放到天平的左右．别忘了在命题C里面，我们假设＂额外有无数个标准品＂可供我们利用，但这个条件在本题不适用，所以上式必须改写为：
　－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
　f(m+1) = 第一秤天平左右两端一共有 (3^m)-1 个物件，若不平衡必能用命题C解决
　 　 　 　＋
　　 　如果第一秤平衡了，则在少了一秤的情况下，我们必须能够解决剩下的q个物件
　－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

好，接下来再看第二条：＂在少了一秤的情况下，必须解决剩下的q个物件＂，请问q是多少？不就是 f(m) 吗？想想看前面的定义， f(m) 与 f(m+1) 相比，正是少用一秤所能解决的物件数量．所以上面公式可以改写为：
　－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
　f(m+1) = 第一秤天平左右两端一共有 (3^m)-1 个物件，若不平衡必能用命题C解决
　 　 　 　＋
　　 　如果第一秤平衡了，则在少了一秤的情况下，我们可以解决 f(m) 个物件
　－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

事实上这公式还有错．当初我们设计 (3^m)-1 这个数字的时候，由於 3^m 是奇数，在没有＂额外的标准品＂可以利用的情况之下，我们无法将 3^m 个物件分放到天平的两端，因此我们才忍痛减1．
然而反观在第一秤平衡之後，当我们处理剩下的 q 个物件的时候，我们手边可是有标准品能够使用的！这与 f(m) 的情况不完全相同．在处理剩下的 q 个物件时，我们可以完全照抄命题C，不必再刻意地减 1 ．因此 q = f(m)+1，而上述公式也可以改写为最终型态：

f(m+1)
= (3^m)-1 + f(m)+1
= 3^m + f(m)

使用穷举实验，我们知道秤2次时最多只能处理4个物件，即 f(2)=4，故：
f(3) = 3^2 + f(2) = 9+4 = 13
f(4) = 3^3 + f(3) = 27+13 = 40
f(5) = 3^4 + f(4) = 81+40 = 121
均合乎预期．

接下来我们开始化简：
f(2) = 4
　f(3) = 3^2 + f(2)
　f(4) = 3^3 + f(3)
　f(5) = 3^4 + f(4)
　f(6) = 3^5 + f(5)
.....
+ f(n+1) = 3^n + f(n)
--------------------------
f(n+1) = (3^2+...+3^n) +4
　　　　= 3^2*(3^(n-1) - 1)/2 + 4
= (3^(n+1) - 9)/2 + 8/2
= (3^(n+1) - 1)/2

故 f(n) = (3^n -1)/2
证毕．

若称量过程中，已知某个球不可能超重，则将它涂成白色。反之若不可能偏轻，则涂成黑色。

首先证明一个引理：

1. 若每个球的颜色都已知，则最多m次称量，可以挑出3^m个球中唯一的坏球。

引理1的证明：

m=1时，不妨设至少有2个球是白色。将这两个球称一次，若相等，则坏球是第三个。
否则，坏球是轻的那个（因为已知这两个球中没有超重的）。

m>1时，将全部球分成{A,B,C} 3份，每份各n=3^{m-1}个球，且使得A, B所包含的白球数目相等,
都为x个。则A, B所含黑球数也相等，都为y=n-x个。

称量A, B，若A=B，则坏球在C中，由归纳假设，得证。
否则，不妨设A<B，则A中所有球都不可能超重。
而已知A中的y个黑球都不可能偏轻，所以这y个黑球既不超重，也不偏轻，都是好球。
同样的B中的x个白球也都是好球。
将这y+x个好球拿走，坏球只能在剩下的x+y=n=3^{m-1}个球中，由归纳假设，得证。

引理1证毕。

令N=N(m)=(3^m-1)/2, m>1。有：

2. 若额外有 3^{m-1} 个好球，则最多称 m 次，可找出 N+1 个(颜色未知)球中唯一的坏球。
m=2时, N+1=5。读者可自己验证设计方案，验证引理2的结论（需要稍微动动脑子）。

m>2时，N=3k+1，其中k=N(m-1)=(3^{m-1}-1)/2。

令x=3^{m-1}, y=k+1, 则x+y=N+1。将N+1个球分成A, B两组，
|A|=x, |B|=y，取x个好球C，比较A, C。
若A=C，坏球在B中，由归纳假设，得证。
否则，坏球在A中，不妨设A<C，A中所有球全涂白，由引理1，得证。
引理2证毕。

3. 最多称 m 次，可找出 N 个球中唯一的坏球。

因N=3k+1，可将这N个球分作{A,B,C,1}四份，
|A|=|B|=|C|=k。
称量 A, B。若A=B，则坏球在剩下的k+1个球C+1中，且A, B的所有2k个球都是好球，
由引理2，得证。
否则，不妨设A<B，则A中所有球都涂白，B中所有球都涂黑。
将A,B的球合在一起，再添一个好球，不妨将这好球涂白。一共有
2k+1=3^{m-1}个球，由引理1，得证。

完毕。

找次品的问题是有规律的。
一般都是分成a a b三份。b可以等于a。b也可可能等于a+1或者a-1，根据总数决定。
把两个a放在天平两端，如果天平平衡，次品就在b里头，如果天平不平衡，则根据次品和正品的差别找出次品在哪一份。
找到之后继续往下分三份。
这样一次就能排除掉三分之二，是最快的。

称m次最多可以从n=3^m个产品中找出那一个次品，即每次称的产品都恰好分成三份，因为若是第三份少了，则m不变的情况下n变小，若是第三份多了，则需要多称一次，m需要加一

则称m-1次最多可以从3^(m-1)个产品中找出那一个次品
因此设称m次可以从n件产品中找出唯一的次品
则3^(m-1)<n≤3^m

(3^m-1)/2 -3^(m-1)
=3^m/2-3^(m-1)-1/2
=(3/2-1)3^(m-1)-1/2
=(1/2)3^(m-1)-1/2
=(1/2)[3^(m-1)-1]>0

3^m-(3^m-1)/2
=(1/2)3^m+1/2
=(1/2)(3^m+1)>0
因此3^(m-1)<(3^m-1)/2≤3^m
命题得证

学了信息论就可以轻松解决了.
假如用logx表示以2为底x的对数的话.
N个零件中告诉你哪个是次品的的信息量为logN bit
天平称一次的信息量有log3 bit
要获得足够的信息量, 假设需要k次, 那么
k * log3 >= logN
k >= ( log( 3^m -1 ) - 1 ) / log3
当m>1时
( log( 3^m -1 ) - 1 ) / log3
=m - q (其中0 < q < 1 )
由于结果必须是整数, 所以向上取整.
此时需要m次就能称出来.

证毕.

证明：由题可得：∵是“最多”，而实际情况（如以2个为一组称量）最多不只m种
又∵N=(3^m-1)/2
∴可知题中“最多”的规则为：去掉某些零件分为3份再比较
又∵每称量1次时，无论是去掉1个或者2个零件
下一次称量时必又算入总数再重新剔除，然后分为3份
设每次称量后的一小份零件个数为n
当称到m-1次时，n=[3-3^(1-m)]/2
m≥2 ==> 1-m≤-1 ==> 0<3^(1-m)<1/3 ==> 8/3<3-3^(1-m)<3
==> 4/3<[3-3^(1-m)]/2<3/2
∵4/3，3/2>1
∴至此还剩2个零件没有称量，无法区分
∴得证，最多称m次

---

黔东南苗族侗族自治州19878559770： 砝码称重问题怎么用贪心算法解决砝码称重问题:设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其质量 - ？
唐月孟得：[答案] 现有1g、2g、3g、5g、10g、20g的砝码各若干枚,问用这些砝码可以称出多少种不同的重量.(设砝码的总重量不超过1000克,且砝码只能放在天平的一端) 输入方式:a1 a2 a3 a4 a5 a6 (表示1g砝码有a1个,2g砝码有a2个,.20g砝码有a6个) ...

黔东南苗族侗族自治州19878559770： 一道关于数学砝码的题目 要把300克盐平均分成三次,有一架天平和5克、30克的砝码各一个,如果要求称的次数越少越好,那么最少要称几次? - ？
唐月孟得：[答案] 第一次,称出35,(30+5) 第二次,35+35=70,(砝码+已经称出的盐) 第三次,70+30=100,(两次的盐+30) 第四次,100克

黔东南苗族侗族自治州19878559770： 经典数学问题:砝码问题 - ？
唐月孟得： 答案是1,3,9,27 做这种题当然要有灵感,如果不考虑到是天平,砝码不光可以放到右盘,用来加.还可以放到左盘,用来减,那么肯定得不出正确答案. 其实做数学题,有些难题可能几天也解不出,但无意中想到一种思路,一下就解出来了. 这也是解数学题的乐趣.

黔东南苗族侗族自治州19878559770： 用三个砝码称出1—40克的重量,三个砝码分别为多少? - ？
唐月孟得：[答案] 这个在数学上叫做梅氏砝码问题,其叙述如下: 若有n个砝码,重量分别为M1,M2,……,Mn,且能称出从1到(M1+M2+……+Mn)的所有重量,则再加一个砝码,重量为Mn+1=(M1+M2+……+Mn)*2+1,则这n+1个砝码能称出从1到 (M1+M2+……+...

黔东南苗族侗族自治州19878559770： 在天平的左盘放砝码,右盘放物体,至少要准备几个砝码,才能称1克到125克之间无论多少克重的物体?这几个砝码分别有多重? - ？
唐月孟得：[答案] 要回答这个问题,你首先必须知道实验室砝码的规格,一般来说实验室的砝码标值是这样的:100g、50g、20g、10g、5g、2g、1g就可以啦

黔东南苗族侗族自治州19878559770： 小学数学问题,请人帮忙解答,解法尽量简单: 有1g,2g,4g,5g,10g砝码各一个,可以称出多少种不同的质量. - ？
唐月孟得：[答案] 1g--22g都可以称出来,也就是22种1=12=23=1+24=45=56=2+47=2+58=1+2+59=4+510=1011=1+1012=2+1013=1+2+1014=4+1015=5+1016=1+5+1017=2+5+1018=1+2+5+1019=4+5+1020=1+4+5+1021=2+4+5+1022=1+2+4+5+10

黔东南苗族侗族自治州19878559770： 关于砝码的问题1.若用破损的砝码来称,质量与原来相比,减小还是增大 2,若用生锈的砝码来称,质量与原来相比,减小还是增大 3,若用破损加生锈的砝... - ？
唐月孟得：[答案] 1 增大 因为砝码破损砝码自身重量减轻,称出来的值就比实际值大 2 减小,生锈了砝码质量增加 3 这个要看破损和生锈的程度而定

黔东南苗族侗族自治州19878559770： 数学问题如果一台天平在称物体时,允许两盘都可以放砝码,那么称1克到13克的重量,只要三只砝码就行了,这3只砝码分别是多少克? - ？
唐月孟得：[答案] 1g 3g 9g 1 = + 1 2 = + 3 - 1 3 = + 3 4 = + 3 + 1 5 = + 9 - 3 - 1 6 = + 9 - 3 7 = + 9 - 3 + 1 8 = + 9 - 1 9 = + 9 10 = + 9 + 1 11 = + 9 + 3 - 1 12 = + 9 + 3 13 = + 9 + 3 + 1 (-表示放物品同侧, +表示放不同侧)

黔东南苗族侗族自治州19878559770： 一共12个砝码,其中有一个不准的(没说更重还是更轻),用天平秤3次,就可得问题砝码是哪个.请写出秤的方法.如果坏的砝码比正常砝码重呢? - ？
唐月孟得：[答案] (1)如果事先知道坏的砝码比正常砝码轻的话,则具体称法为:第一次:两边各放六个,把重的一边六个排除掉第二次:两边各方三个,把重的一边三个排除掉第三次:任意取两个砝码放在两边, a).如果两边一样...

黔东南苗族侗族自治州19878559770： 现有1克,2克,4克,8克,16克的砝码各一枚,问在天平上能称多少种不同重量的物体?解题思路是 - ？
唐月孟得： 每个砝码都可以选择用或不用,就相当于二进制中的0(不用)和1(用).这五个砝码的特点是,所有砝码质量都是2的整数次幂,每个砝码的质量均大于它前边所有砝码质量和,所以称出的质量可以表示为二进制数:如21g:10101;14g:01110.那么非零的五位的二进制数总数即为本题答案:2^5-1=31(1~31g)