想了很久,请大家帮忙看看

昨天面试官问了一道编程题:
现在有三个打印机,假设每个打印机都是一样的。
然后现在有一个数组,数组里面存着大于零的整数,数组里存储的数字代表一个打印任务,数值是完成这个打印任务需要的时长。
请问该用怎么样的策略来分配任务给打印机,能使得完成所有任务的时间最短?


举个例子:
假设有任务:5,5,5,6,7,8,9
我们给每台打印机分配任务:
打印机A:5,5,5
打印机B:6,9
打印机C:7,8
这样完成所有任务的时间就是15,也就是最短的时间。
#面试题目#
全部评论
或者用dfs呢,直接暴力搜索
点赞 回复 分享
发布于 2020-09-13 14:56
这是np完全问题,没有最优解
点赞 回复 分享
发布于 2020-09-13 10:07
动态规划?最理想的最短时间就是每个打印机的工作时间是总时长的三分之一。先求最接近小余等于三分之一的情况,然后求解剩下的最接***分的情况。不过这样好像不方面求的具体方案啊。。
点赞 回复 分享
发布于 2020-09-13 00:23
贪心?
点赞 回复 分享
发布于 2020-09-12 23:10
二分最短时间?
点赞 回复 分享
发布于 2020-09-12 23:09
我当时的思路是将所有任务排序,从最大的开始分配,每次将任务分给目前任务最少的打印机,但是面试官说不对,能举出反例。当时没想出来反例是什么,现在发现确实有反例,就是描述中的例子
点赞 回复 分享
发布于 2020-09-12 22:58

相关推荐

点赞 评论 收藏
分享
07-09 20:50
门头沟学院 Java
码农索隆:1.教育背景和荣誉证书合二为一。 2.获奖项目理一遍,你做了什么,对你求职的岗位有什么帮助,没有就删掉。 3.技能特长和教育背景交换位置。 4.技能特长写的太差,上网上找简历参考。都不用问你别的,一个redis就能把你问住,写写你具体会redis哪些方面的知识。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-30 18:02
投递京东等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务