知道砝碼稱重問題【問題描述】 設(shè)有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重<=1000），用他們能稱出的重量的種類數(shù)。
【輸入文件】
a1 a2 a3 a4 a5 a6
（表示1g砝碼有a1個，2g砝碼有a2個，…，20g砝碼有a6個，中間有空格）。
【輸出文件】
Total=N
（N表示用這些砝碼能稱出的不同重量的個數(shù)，但不括個砝碼也不用的情況）。
【輸入樣例】
1 1 0 0 0 0
【輸出樣例】
Total=3 枚舉法
【還是犯了些錯的 比如 read寫成readln 還有循環(huán)時把w[1]的循環(huán)寫成1→g[1]了（應(yīng)該是0→g[1]） 結(jié)果莫名沒過3個點 殘念】 材質(zhì)種類— 無磁不銹鋼.非磁性不銹鋼，銅鍍鉻，鐵鍍鉻。
砝碼形狀— 園柱體.園錐體.板形.片形.圈（環(huán)）形.騎形.條（棒）形
組合形式— 常規(guī)組合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，然后統(tǒng)計有幾種不同的重量。用數(shù)組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循環(huán)可以算出總重量sum，剩下的工作就是要判斷sum是否已經(jīng)出現(xiàn)過即判重。要實現(xiàn)這點很簡單，注意到條件：其總重<=1000，可以開個[0..1000]的boolean數(shù)組H，設(shè)初值為false,然后H[sum]:=true，zui后統(tǒng)計在H[1..1000]中有幾個true即可。
總結(jié)：此枚舉算法著實弱智，但事實上此算法可以通過所有的測試數(shù)據(jù)，在比賽中使用可以省時省力。因此我們要改變印象中枚舉算法是低效的觀念，在沒有方法時，枚舉往往是突破口。 DP法
【就是個01背……但是我zui悲哀的是忘了初始化 好容易想明白為什么必須要f[0]:=true;結(jié)果還忘了寫……】
【把問題稍做個改動，已知a1+a2+a3+a4+a5+a6個砝碼的重量w[i], w[i]∈{ 1,2,3,5,10,20} 其中砝碼重量可以相等，求用這些砝碼可稱出的不同重量的個數(shù)?！?br />【這樣改就是經(jīng)典的0/1背問題的簡化版了，求解方法*和上面說的樣，這里就不多說了，只是要注意這個題目不是求zui載重量，是統(tǒng)計所有的可稱出的重量的個數(shù)?！?br />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. 什么叫做砝碼？
具有給定質(zhì)量和規(guī)定形狀的實物量具。供檢定衡器和在衡器上行衡量時使用。砝碼必須與天平或秤相結(jié)合（用于秤上的砝碼常稱為砣），才能用于測定其他物體的質(zhì)量，故它是種從屬的實物量具。中在夏代即出現(xiàn)相當(dāng)于砝碼的“權(quán)”。此后的4000多年間，不同朝代有不同形狀和材質(zhì)的“權(quán)”作為衡量的量具。在現(xiàn)代質(zhì)量計量中，砝碼是質(zhì)量量值傳遞的標(biāo)準(zhǔn)量具。質(zhì)量量值以保存在法計量局的鉑銥合金千克原器實物為*基準(zhǔn)器。各均將砝碼分為家千克基準(zhǔn)、家千克副基準(zhǔn)、千克工作基準(zhǔn)，以及由千克的倍量和分量構(gòu)成的工作基準(zhǔn)組和各等工作標(biāo)準(zhǔn)砝碼。家千克基準(zhǔn)各均只有個。中的家千克基準(zhǔn)是1965年由計量局檢定、編號為60的鉑銥合金千克基準(zhǔn)砝碼。家千克基準(zhǔn)與家作證基準(zhǔn)、家千克副基準(zhǔn)、千克工作基準(zhǔn)、標(biāo)準(zhǔn)砝碼組成質(zhì)量量值傳遞系統(tǒng)。為衡量各種不同質(zhì)量的物體，千克工作基準(zhǔn)配有套由其倍量和分量組成的、質(zhì)量由到小、個數(shù)zui少而又能組成任何量值的工作基準(zhǔn)組。工作基準(zhǔn)組及標(biāo)準(zhǔn)砝碼通常分為千克組（120kg）、克組 （150g）和毫克組（1500mg），根據(jù)需要還可以有微克組或其他種砝碼組合（如在臺秤上采用的增砣組）。砝碼的組合形式通常有 5、3、2、1，5、2、2、1和5、2、1、1。
請查看：http://dl-csj.cn/ |
