贪婪法
有n吨货物,用10吨,5吨,3吨的货车来运输,怎样调用用车最少。(使用贪婪法)
题目没贴全吧,
如果只是要用车最少,那都用10吨的车,车辆数目是 (n+9)/10
程序代码:/*
5吨的车不能超过1辆,否则就可以用1辆10吨的车替代;同理,3吨的车不能超过4辆。
于是得出下表:
0辆5吨的车 + 0辆3吨的车 = 00吨
0辆5吨的车 + 1辆3吨的车 = 03吨
0辆5吨的车 + 2辆3吨的车 = 06吨
0辆5吨的车 + 3辆3吨的车 = 09吨
0辆5吨的车 + 4辆3吨的车 = 12吨
1辆5吨的车 + 0辆3吨的车 = 05吨
1辆5吨的车 + 1辆3吨的车 = 08吨
1辆5吨的车 + 2辆3吨的车 = 11吨
1辆5吨的车 + 3辆3吨的车 = 14吨
1辆5吨的车 + 4辆3吨的车 = 17吨
上表中,个位数从0到9都有了,很棒!
*/
#include <stdio.h>
int main( void )
{
const unsigned table[10][3] = { 0,0,0, 1,2,1, 0,4,1, 0,1,0, 1,3,1, 1,0,0, 0,2,0, 1,4,1, 1,1,0, 0,3,0 };
for( unsigned n; scanf("%u",&n)==1 && n!=1 && n!=2 && n!=4 && n!=7; )
{
const unsigned* p = table[n%10];
printf( "需要 %u 辆10吨的车,%u 辆5吨的车,%u 辆3吨的车\n", n/10-p[2], p[0], p[1] );
}
}