两个算法题

medie2005 · 发表于 2010-5-15 10:22:55

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

1、自动打开一个文本文件，读取文本文件中的表格（N列*N行），格式自定有N个机器及N个任务，大概如下 JOB Job 1 Job 2 Job 3 Job 4 Machine 1 14 5 8 7 Machine 2 2 12 6 5 Machine 3 7 8 3 9 Machine 4 2 4 6 10 每个机器完成不同的任务所需的时间是不同的，且机器只能被分配一个任务，不需要考虑重新利用问题，求最短的分配方案 2、自动打开一个文本文件，读取文本文件中的表格（N列*N行），格式自定里面的表格代表的是有 N个村庄，表格列出了每个村庄到其他村庄的距离 From Village 1 Village 2 Village 3 Village 4 Village 5 Village 6 Village 1 0 10 20 30 30 20 Village 2 10 0 25 35 20 10 Village 3 20 25 0 15 30 20 Village 4 30 35 15 0 15 25 Village 5 30 20 30 15 0 14 Village 6 20 10 20 25 14 0 现在想造消防站，求最少需要造几个消防站，这样可以让任意村庄都至少有一个消防站可以在15分钟内到达

litaoye · 发表于 2010-5-16 22:34:28

medie2005也看到这两个问题了么？好奇怪，最近讨论规划问题的特别多。第一题匈牙利算法，复杂度大概n^3 第二题应该还是最小顶点覆盖的问题

mathe · 发表于 2010-5-17 09:42:57

第一题应该是指派问题，我记得是运筹学里面的。

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 两个算法题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。