| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 105 人关注过本帖, 1 人收藏
标题:贪婪法
只看楼主 加入收藏
宏福苑
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2018-12-7
结帖率:0
  已结贴   问题点数:20  回复次数:2   
贪婪法
有n吨货物,用10吨,5吨,3吨的货车来运输,怎样调用用车最少。(使用贪婪法)
2018-12-07 13:58
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:273
帖 子:6001
专家分:34326
注 册:2011-1-18
  得分:20 
题目没贴全吧,
如果只是要用车最少,那都用10吨的车,车辆数目是 (n+9)/10
2018-12-07 14:09
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:273
帖 子:6001
专家分:34326
注 册:2011-1-18
  得分:0 
如果说不允许不装满,那 n=1、2、4、7 时怎么办?

程序代码:
/*
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] );
    }
}

2018-12-07 14:35







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024631 second(s), 8 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved