知道砝码称重问题【问题描述】 设有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 枚举法
【还是犯了些错的 比如 read写成readln 还有循环时把w[1]的循环写成1→g[1]了（应该是0→g[1]） 结果莫名没过3个点 残念】 材质种类— 无磁不锈钢.非磁性不锈钢，铜镀铬，铁镀铬。
砝码形状— 园柱体.园锥体.板形.片形.圈（环）形.骑形.条（棒）形
组合形式— 常规组合5.2.2.1，（可按用户需求任意组合）
精度等级— 等（E2）. 二等（F1实差）. F1 （三级允差）. F2 （四级）. M1 （五级）. M2（六级）
【显然写的太长了……ORZ】
program weight;
const w:array[1..6] of integer=（1,2,3,5,10,20）;
var i,j,k,l,m,n,total,sum:longint;
g:Array [1..6] of integer;
f:array[1..1000] of boolean; begin
assign（input,'weight.in'）;
reset（input）;
assign（output,'weight.out'）;
rewrite（output）; sum:=0;
total:=0;
for i:=1 to 6 do
begin
read（g[i]）;
end; for i:=1 to g[1] do
begin
sum:=w[1]*i;
if not f[sum] then
begin
f[sum]:=true;
inc（total）;
end;
end; for i:=1 to g[2] do
begin
sum:=w[2]*i;
if not f[sum] then
begin
f[sum]:=true;
inc（total）;
end;
end; for i:=1 to g[3] do
begin
sum:=w[3]*i;
if not f[sum] then
begin
f[sum]:=true;
inc（total）;
end;
end; for i:=1 to g[4] do
begin
sum:=w[4]*i;
if not f[sum] then
begin
f[sum]:=true;
inc（total）;
end;
end; for i:=1 to g[5] do
begin
sum:=w[5]*i;
if not f[sum] then
begin
f[sum]:=true;
inc（total）;
end;
end; for i:=1 to g[6] do
begin
sum:=w[6]*i;
if not f[sum] then
begin
f[sum]:=true;
inc（total）;
end;
end;
for i:=0 to g[6] do
for j:=0 to g[5] do
for k:=0 to g[4] do
for l:=0 to g[3] do
for m:=0 to g[2] do
for n:=0 to g[1] do
begin
sum:=w[1]*n+w[2]*m+w[3]*l+w[4]*k+w[5]*j+w[6]*i;
if not f[sum] then
begin
f[sum]:=true;
inc（total）;
end;
end;
wrin（'Total=',total-1）;
close（input）;
close（output）;
end. 枚举简易法
zui容易想到的方法就是枚举出有几个1g，几个2g，几个3g……几个20g，然后统计有几种不同的重量。用数组w[1]~w[6]表示重量，q[1]~q[6]表示选择方案。算法描述如下（Pascal语言）：
for q[1]:=0 to a1 do
for q[2]:=0 to a2 do
for q[3]:=0 to a3 do
for q[4]:=0 to a4 do
for q[5]:=0 to a5 do
for q[6]:=0 to a6 do begin
sum:=0;
for i:=1 to 6 do sum:=sum+q[i]*w[i];
end;
利用6个for循环可以算出总重量sum，剩下的工作就是要判断sum是否已经出现过即判重。要实现这点很简单，注意到条件：其总重<=1000，可以开个[0..1000]的boolean数组H，设初值为false,然后H[sum]:=true，zui后统计在H[1..1000]中有几个true即可。
总结：此枚举算法着实弱智，但事实上此算法可以通过所有的测试数据，在比赛中使用可以省时省力。因此我们要改变印象中枚举算法是低效的观念，在没有方法时，枚举往往是突破口。 DP法
【就是个01背……但是我zui悲哀的是忘了初始化 好容易想明白为什么必须要f[0]:=true;结果还忘了写……】
【把问题稍做个改动，已知a1+a2+a3+a4+a5+a6个砝码的重量w[i], w[i]∈{ 1,2,3,5,10,20} 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。】
【这样改就是经典的0/1背问题的简化版了，求解方法*和上面说的样，这里就不多说了，只是要注意这个题目不是求zui载重量，是统计所有的可称出的重量的个数。】
program weight_DP;
const maxn=1005;
w:array [1..6] of integer=（1,2,3,5,10,20）;
var i,j,k,total:longint;
a:array[1..6] of integer;
f:array[0..maxn] of boolean; begin
assign（input,'weight.in'）;
reset（input）;
assign（output,'weight.out'）;
rewrite（output）; total:=0;
fillchar（f,sizeof（f）,false）;
for i:=1 to 6 do
read（a[i]）; f[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
begin
if f[k-w[i]] then f[k]:=true;
end;
for i:=1 to maxn do
if f[i] then inc（total）;
wrin（'Total=',total）; close（input）;
close（output）;
end. 什么叫做砝码？
具有给定质量和规定形状的实物量具。供检定衡器和在衡器上行衡量时使用。砝码必须与天平或秤相结合（用于秤上的砝码常称为砣），才能用于测定其他物体的质量，故它是种从属的实物量具。中在夏代即出现相当于砝码的“权”。此后的4000多年间，不同朝代有不同形状和材质的“权”作为衡量的量具。在现代质量计量中，砝码是质量量值传递的标准量具。质量量值以保存在法计量局的铂铱合金千克原器实物为*基准器。各均将砝码分为家千克基准、家千克副基准、千克工作基准，以及由千克的倍量和分量构成的工作基准组和各等工作标准砝码。家千克基准各均只有个。中的家千克基准是1965年由计量局检定、编号为60的铂铱合金千克基准砝码。家千克基准与家作证基准、家千克副基准、千克工作基准、标准砝码组成质量量值传递系统。为衡量各种不同质量的物体，千克工作基准配有套由其倍量和分量组成的、质量由到小、个数zui少而又能组成任何量值的工作基准组。工作基准组及标准砝码通常分为千克组（120kg）、克组 （150g）和毫克组（1500mg），根据需要还可以有微克组或其他种砝码组合（如在台秤上采用的增砣组）。砝码的组合形式通常有 5、3、2、1，5、2、2、1和5、2、1、1。
请查看：http://www.21fama.com/ |
