求一个算法,以下是要求!

xinxinboy 2004-04-08 03:29:08
有n个工人他们分别对某个项目的某些任务有具体的经验,现在要求选最少的人完成这个项目.(当然对于某个任务会有一个以上的人会;对于某个人会做一个以上的任务)
问题是:会存在2组以上满足最少的人完成这一项目.要求全部找出来!
...全文
87 34 打赏 收藏 转发到动态 举报
写回复
用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)

7,759

社区成员

发帖
与我相关
我的任务
社区描述
VB 基础类
社区管理员
  • VB基础类社区
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧