簡(jiǎn)答題

　　第一題：7公斤米，50克砝碼，200克砝碼各一個(gè)，稱(chēng)1350克米問(wèn)最少要多少次，并編程回答。

　　我答，6次，可能一開(kāi)始會(huì)想到 1350/250 + 2 = 7次，說(shuō)明貪心無(wú)效。我不知道我的方法是不是很笨，用了遞推，或者你可以看成是動(dòng)態(tài)規(guī)劃。轉(zhuǎn)化一下題目的意思就是1克和4克砝碼，問(wèn)多少次稱(chēng)出27克大米，F(xiàn)[N]代表N克大米最少需要多少次。

　　則有：

　　F[N]=min{F[N-1],F[N-4],F[N-5]}+1

　　代碼如下：

　　intfindmin(int weight)

　　{

　　int v= weight/50;

　　int f[150];

　　f[0]=0;f=1;f=2;f[3]=3;f[4]=1;

　　if (v<5) return f[v];

　　int i;

　　for (i=5;i<=v;i++)

　　f[i]=min(f[i-1]+1,f[i-4]+1,f[i-5]+1);

　　return f[v];

　　}

　　注：我一開(kāi)始愣了很久，我在想，稱(chēng)好的大米可以作為砝碼來(lái)用嗎??這樣就是另一種問(wèn)題了吧。