成本分配问题
我有一个问题，我被困住了，找不到任何地方可以开始，所以我绝望地转向 stackoverflow。
该问题要求我们找出它是 np-hard 还是多项式，如果它的 np-hard 证明 np-completeness，否则给出算法。
问题如下：
一个产品存在n个模块。有两家公司可以构建每个模块，需要一些成本（c_ij，i：模块编号，j：公司编号）。如果模块 a 和 b 由不同的公司构建，它们也会产生额外的成本 (p_ab)。模块a和b不必是连续的，同样的额外成本也适用于a和c。正如预期的那样，该问题希望我们找到将模块分配给公司的方法，以使总成本最小。
有什么想法吗？
i have a problem, which i'm stuck with, and cant find anywhere to start with, so i'm hopelessly turning to stackoverflow.
the problem wants us to find out if it is np-hard or polynomial, if its np-hard prove np-completeness, else give the algorithm.
the problem is as follows:
a product exists of n modules. there are two companies that can build each module, with some cost (c_ij, i: module number, j: company number). if modules a and b are built by different companies, they also have an additional cost, (p_ab). the modules a and b do not have to be successive, the same additional cost applies for a and c too. as expected, the problem wants us to find the assignment of modules to companies so that the total cost is minimum.
any ideas ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
它可以简化为最小割问题，可以通过任何最大流算法找到。
那么什么是网络呢？
模块将是我们图的顶点，我们还添加 2 个新顶点源和汇。
从源头开始，我们为每个容量为 Ci1 的模块 i 添加边缘。类似地，我们在每个模块 i 中添加容量为 Ci2 的边缘到接收器。此外，对于任何模块 i 和 j，我们添加容量为 pij 的边
（面向图，因此将有两条边（ij）和（ji））。很容易看出，最小切割的值是问题的解决方案（切割中的部分模块，源分配给第二家公司，其余模块分配给第一家公司）
It can be reduced to min cut problem, which can be found by any max flow algorithm.
So what's the network?
Modules will be vertecies of our graph and also we add 2 new vertices source and sink.
From source we add edge to every module i with capacity Ci1. Similarly from every module i we add edge to sink with capacity Ci2. Also for any modules i and j we add edge with capacity pij
(graph oriented thus there will be two edges (i j) and (j i)). It is easy to see that value of min cut is solution of the problem (modules in part of the cut with the source assign to the second company and rest modules to the first company)