社区
VB基础类
帖子详情
求一个算法,以下是要求!
xinxinboy
2004-04-08 03:29:08
有n个工人他们分别对某个项目的某些任务有具体的经验,现在要求选最少的人完成这个项目.(当然对于某个任务会有一个以上的人会;对于某个人会做一个以上的任务)
问题是:会存在2组以上满足最少的人完成这一项目.要求全部找出来!
...全文
87
34
打赏
收藏
求一个算法,以下是要求!
有n个工人他们分别对某个项目的某些任务有具体的经验,现在要求选最少的人完成这个项目.(当然对于某个任务会有一个以上的人会;对于某个人会做一个以上的任务) 问题是:会存在2组以上满足最少的人完成这一项目.要求全部找出来!
复制链接
扫一扫
分享
转发到动态
举报
写回复
配置赞助广告
用AI写文章
34 条
回复
切换为时间正序
请发表友善的回复…
发表回复
打赏红包
lsftest
2004-04-09
打赏
举报
回复
但是如果是这种情况怎么办:
1 a,b,c,d,e
2 a,b,c
3 d,e,f
4 f
结果又是(1,4)(2,3)了你的方法好象无法解决哦
===========================
题目介绍得有点虚,试试落实到实际的计算。。一种思路:
把每个工人的技能都转变成为一个字符串(或二进制数),在这个字符串里,懂得相应项技能用1表示,否则用0表示,那么在上面你给出的例子里,就可以把工人的技能变成下面的(以abcdef的顺序排列技能,可以根据技能的种类来调节字符串的位数):
1 a,b,c,d,e 变成字符串“111110”
2 a,b,c 变成字符串“111000”
3 d,e,f 变成字符串“000111”
4 f 变成字符串“000001”
在这里,字符串可以进行加运算,但规则如下:
1+1=1
1+0=1
0+1=1
0+0=0
(这种运算方式在逻辑上好像是有一种专门称呼的,类似同或、异或之类。。但忘了)
所以工人配搭能完成多少个步骤就可以进行运算了,例如:
工人1+工人2=“111110”+“111000”=“111110”
工人2+工人3=“111000”+“000111”=“111111”
很明显,完成整个任务的字符串为“111111”,从而就把题目的要求转变为这样:
使用给出的若干个字符串,最少要做多少次加运算才能得出字符串“111111”?有多少个组合?
如果有时间我也试试写写。。。。。
danielpan
2004-04-09
打赏
举报
回复
明白了,你的解法实际上就是广度优先的,我的是深度优先,复杂度是一样的
danielpan
2004-04-09
打赏
举报
回复
演示中找出来了阿!
lsftest
2004-04-09
打赏
举报
回复
楼上的方法好像就是不太方便找最优解,你要把所有解都找出来以后才知道谁是最优解
============================================================================
不必找出所有解,因为循环当然是由少到多地进行的,就是说,必然是先把工人两两相加看能不能的出任务字符串“111111”,如果能,那么枚举完两两相加就可以结束打印结果。如果不能,才进行下一轮的循环,把工人三三相加。。。如此类推。。。
问题难在组合方面,如果工人数跟步骤数多了很麻烦。。。。
pigpag
2004-04-09
打赏
举报
回复
这只是个建模(其实也没有什么进展的)
danielpan
2004-04-09
打赏
举报
回复
楼上的方法好像就是不太方便找最优解,你要把所有解都找出来以后才知道谁是最优解
lsftest
2004-04-09
打赏
举报
回复
真是晕了头,上面的
1+1=1
1+0=1
0+1=1
0+0=0
运算规则其实就是位的或运算(or)。。。。。
taosihai1only
2004-04-09
打赏
举报
回复
用遍历行了
lsftest
2004-04-09
打赏
举报
回复
如何按照这个法则来进行 工人1+工人2=“111110”+“111000”=“111110”
这样的运算呢?是不是还得一位一位的来验证!有没有什么捷径!
============================================
我上面已经说了,不一定把它存为字符串,也可以把它做成一个二进制数,这样就可以对两个二进制数进行“或”运算了。
xinxinboy
2004-04-09
打赏
举报
回复
......例子我在上面已经举过了!看看先,呵呵
Huaraco
2004-04-09
打赏
举报
回复
不懂意思,举个例子好吗?
xinxinboy
2004-04-09
打赏
举报
回复
1+1=1
1+0=1
0+1=1
0+0=0
如何按照这个法则来进行 工人1+工人2=“111110”+“111000”=“111110”
这样的运算呢?是不是还得一位一位的来验证!有没有什么捷径!
douhapy
2004-04-09
打赏
举报
回复
太复杂了,还是有点不明白题目的意思
lsftest
2004-04-08
打赏
举报
回复
但是如果是这种情况怎么办:
1 a,b,c,d,e
2 a,b,c
3 d,e,f
4 f
结果又是(1,4)(2,3)了你的方法好象无法解决哦
=====================================================
这种情况应该还有一组解(1,3)。。
danielpan
2004-04-08
打赏
举报
回复
111269(连)
这里的朋友加我记得注明csdn
guliang3333
2004-04-08
打赏
举报
回复
太深奥了,没看懂。
xinxinboy
2004-04-08
打赏
举报
回复
留下你的qq好吗,我们改天再谈,我要出去上会儿自习!这段时间学校不准上网
xinxinboy
2004-04-08
打赏
举报
回复
恩,是可以暂时解决问题了!你等等,我再找以下茬,呵呵!
danielpan
2004-04-08
打赏
举报
回复
但是如果是这种情况怎么办:
1 a,b,c,d,e
2 a,b,c
3 d,e,f
4 f
结果又是(1,4)(2,3)了你的方法好象无法解决哦
再来解一次:
首先是
1 a,b,c,d,e
2 a,b,c
3 d,e,f
4 f
选1,然后剩下
2
3 f
4 f
然后选3,剩下
4
2
找到一组解,输出.返回到选3之前,现在剩下(3已经去掉了,其实2也可以去掉,应为他已经是空了)
2
4 f
选4,剩下
2 (或者剩下空,如果前面把2去掉的话)
找到解,输出.返回到选1前,也就是最开始,把1去掉
2 a,b,c
3 d,e,f
4 f
选2,剩下
3 d,e,f
4 f
选3,剩下
4
找到解,输出.返回到选3前
剩下
4 f
不能完成,返回到选2前
剩下
3 d,e,f
4 f
不能完成任务,无解(一共找到3组解).
这实际上是个递归的调用过程了,只不过帮你把过程都分析了一下,可能也是我没讲清楚.
danielpan
2004-04-08
打赏
举报
回复
就拿上面楼主举的例子来说吧
员工 任务
第一个人(员工A): a,b,c,e
第二个人(员工B): c,d,f
第三个人(员工C): d,f
先排序,顺序是A,B,C
然后选出A,那么剩下了B,C
把A包含的技能在B,C中去掉,那么变成了
B:d,f
C:d,f
由于两个人会的一样,所以排不排序都一样.
选B,剩下C
把B包含的技能在C中去掉,那么变成了
C:
由于剩下的人中间的技能都是空,所以找到了一组解,输出.
返回到上一步,也就是选B前那步,这次我们不选B(以后也永远不选B了),选C
那么去掉C的技能后,成了
(空,因为我们不考虑B了,当然如果有B的话,也是B空拉,但是如果人更多,就要把B去掉)
剩下的部分没有任何技能,又是一组解,输出.
再返回,这次我们到了最开始,要把A直接去掉.
但是下来发现完不成任务.
至此已经全部搜索完了,找到2组解.
加载更多回复(14)
(
算法
)通俗易懂的字符串匹配KMP
算法
及
求
next值
算法
大多数据结构课本中,串涉及的内容即串的模式匹配,需要掌握的是朴素
算法
、KMP
算法
及next值的
求
法。在考研备考中,参考严奶奶的教材,我也是在关于
求
next值的
算法
中卡了一下午时间,感觉挺有意思的,把一些思考的结果整理出来,与大家一起探讨。
以下
的顺序为 1、最基本的朴素
算法
2、优化的KMP
算法
3、应
算法
需要定义的next值 4、手动写出较短串的next值的方法 5、最难理解的、足足有5行的代码...
用计算机程序
求
n,计算机编程
算法
求
n!.doc
计算机编程
算法
求
n!.doc
算法
:
求
n!任务通过对“n!”(n阶乘)这个
算法
的描述以及程序实现的方法,了解循环结构
算法
的特征,掌握“累乘器”的
算法
及程序设计。对于“
求
n!”这个问题,高中学生不是很清楚,所以应该对n!的定义进行
一个
说明。并理解用计算机来
求
解n!的一种
算法
,一、什么是n!在函数型计算器上有
一个
特殊的按钮,就是“n!”,称为“阶乘”,在数学上表示从1一直累乘到n,即n!=1*2*3...
算法
1.
算法
定义
算法
(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,
算法
代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所
要
求
的输出。如果
一个
算法
有缺陷,或不适合于某个问题,执行这个
算法
将不会解决这个问题。不同的
算法
可能用不同的时间、空间或效率来完成同样的任务。
一个
算法
的优劣可以用空间复杂度与时间复杂度来衡量。
【
算法
】
求
最短路径
算法
从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径叫做最短路径。解决最短路径的问题有
以下
算法
:Dijkstra
算法
,Bellman-Ford
算法
,Floyd
算法
和 SPFA
算法
等。迪杰斯特拉
算法
(Dijkstra
算法
)是典型最短路径
算法
,用于计算
一个
节点到其它节点的最短路径,它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。该
算法
的时间复杂度为 O(ElogV),其中 E 为边数,V 为节点数。
算法
概述——四大
算法
总结
解决
一个
问题具体方法或者说过程,也就是能根据实际情况输入对应条件,在有限的时间内获得所
要
求
的结果。因为计算机的运算资源和存储容器是有限的,为了保证程序的**执行效率**,我们需要再面对具体问题时采用合适的
算法
去处理问题,而解决同
一个
问题的不同的
算法
的效率可能会相差非常大,
算法
效率的差距影响有时甚至比计算机配置的差距还要更大,所以面对问题时
一个
正确的合适的
算法
至关重要!
算法
和数据结构构成可运行程序,
算法
是程序的灵魂!
VB基础类
7,759
社区成员
197,606
社区内容
发帖
与我相关
我的任务
VB基础类
VB 基础类
复制链接
扫一扫
分享
社区描述
VB 基础类
社区管理员
加入社区
获取链接或二维码
近7日
近30日
至今
加载中
查看更多榜单
社区公告
暂无公告
试试用AI创作助手写篇文章吧
+ 用AI写文章