淘宝实习招聘笔试题(2)

　　简答题

　　第一题：7公斤米，50克砝码，200克砝码各一个，称1350克米问最少要多少次，并编程回答。

　　我答，6次，可能一开始会想到 1350/250 + 2 = 7次，说明贪心无效。我不知道我的方法是不是很笨，用了递推，或者你可以看成是动态规划。转化一下题目的意思就是1克和4克砝码，问多少次称出27克大米，F[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]=1;f[2]=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];

　　}

　　注：我一开始愣了很久，我在想，称好的大米可以作为砝码来用吗??这样就是另一种问题了吧。