mrblbl 2019-05-27 09:21
浏览 293

NP-completeness 的推导

分区问题算法 (partition problem):给定一组整数S,能否找到两个子数组,
使得这两个数组的和相等。 两个子数组必须包含所有S中的数。


需要推导的算法:
1. 给定一个无向图 G = (V, E), 所有的路径 e 都有一个非负长度 l(e) 和
非负费用 c(e)。
2. 在 V 内, 有一个始发点 (source vertex) s 和 一个终点(destination vertex) t
3. 给定最大非负长度 L 和 最大非负费用 C。

判断是否存在一条简单路径从 s 到 t,长度总和小于 L 并且费用总和小于 C


一直没想到如何构造这个图,使得这个算法能返回正确的分区。

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 程序实在不会写,要秃了
    • ¥15 pycharm导入不了自己的包
    • ¥15 C#.net通过内网url地址获取文件并下载问题,浏览器postman可以正常下载,用程序不行
    • ¥15 本人本科机械,目前研一。没有深度学习基础,目前对研究生课题一片迷茫,请教各位!
    • ¥15 关于R语言单因素与多因素线性回归的平均值
    • ¥15 服务器清除BIOS之后引导不了
    • ¥15 CPLEX用OPL编写的混合整数线性优化问题。
    • ¥15 可以用EasyConnect连接实验室内网,但无法连接内网才能访问的服务器,为什么?
    • ¥15 前端预览docx文件,文件从后端传送过来。
    • ¥15 层次聚类和蛋白质相似度