我有一个问题,我被困住了,找不到任何开始的地方,所以我绝望地转向stackoverflow。
问题要我们找出它是 np-hard 还是多项式,如果它的 np-hard 证明 np-completeness,否则给出算法。
问题如下:
存在 n 个模块的乘积。有两家公司可以构建每个模块,但需要一些成本(c_ij,i:模块编号,j:公司编号)。如果模块 a 和 b 是由不同的公司构建的,它们也会产生额外的成本 (p_ab)。模块 a 和 b 不必连续,同样的额外费用也适用于 a 和 c。正如预期的那样,问题要我们找到将模块分配给公司的方法,以使总成本最小。
有任何想法吗 ?