贪婪法
有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] ); } }