NP完全问题实际应用题目
某街道给封控在家的居民们发来了大礼包，大礼包里包含 N 种不同的瓜果
蔬菜。居民们在探究如何更有效地把这些原材料组合做出更美味的菜肴。假定给
出大小为 的矩阵 a，矩阵中每个位置的元素 a[i][j] 代表第 i 种蔬菜和
第 j 种蔬菜的排斥程度，a[i][j]越小证明这两种蔬菜越适配，越大越排斥。假设 N=3
时，给定对称矩阵如下：
1
2
3
1
0.0
0.6
0.2
2
0.6
0.0
0.1
3
0.2
0.1
0.0
例如，对角线上的元素全都是 0，证明第 i 种蔬菜和自己完美搭配，但是第 1 种
蔬菜和第 2 种蔬菜的匹配程度不够好。假设居民选择某种蔬菜集合，定义该集
合的总排斥度为
。在上述给定匹配矩阵中，选取全部三种
蔬菜 时的总排斥度
。
问题 1：给定蔬菜总数与对应大小为 的排斥矩阵 a、及 希望搭配的蔬菜总
类个数，即
，其中
代表集合的元素个数。求解种蔬菜可以组成的
最小总排斥度
、以及对应的蔬菜集合，并给出对应的时间、空间计算复杂度。
M=1/2/3 时解如何？M 时解如何？
问题 2：给定蔬菜总数与对应大小为 的排斥矩阵 a、及 希望得到的最小总
排斥度上限，求解
。
