知道砝碼稱重問題

【問題描述】

    設(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]了（應該是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ù)。】
【這樣改就是經(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)相當于砝碼的“權(quán)”。此后的4000多年間，不同朝代有不同形狀和材質(zhì)的“權(quán)”作為衡量的量具。在現(xiàn)代質(zhì)量計量中，砝碼是質(zhì)量量值傳遞的標準量具。質(zhì)量量值以保存在法計量局的鉑銥合金千克原器實物為*基準器。各均將砝碼分為家千克基準、家千克副基準、千克工作基準，以及由千克的倍量和分量構(gòu)成的工作基準組和各等工作標準砝碼。家千克基準各均只有個。中的家千克基準是1965年由計量局檢定、編號為60的鉑銥合金千克基準砝碼。家千克基準與家作證基準、家千克副基準、千克工作基準、標準砝碼組成質(zhì)量量值傳遞系統(tǒng)。為衡量各種不同質(zhì)量的物體，千克工作基準配有套由其倍量和分量組成的、質(zhì)量由到小、個數(shù)zui少而又能組成任何量值的工作基準組。工作基準組及標準砝碼通常分為千克組（120kg）、克組 （150g）和毫克組（1500mg），根據(jù)需要還可以有微克組或其他種砝碼組合（如在臺秤上采用的增砣組）。砝碼的組合形式通常有 5、3、2、1，5、2、2、1和5、2、1、1。
 

       請查看：http://www.21fama.com/