【23xiu.com-爱上秀-教育信息门户网】
简答题
第一题：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];
}
注：我一开始愣了很久，我在想，称好的大米可以作为砝码来用吗??这样就是另一种问题了吧。