我正在阅读一个问题,并试图解决这个问题.
你邀请了N个人吃饭.让我们说4.
你有一个圆形餐桌,你希望周围的每个人都坐下来.不幸的是,并非所有的朋友都是彼此的朋友,但你希望以最佳方式安排每个人,以便让尽可能多的人坐在他们认为是朋友而不是敌人的人旁边.
你已经用大小为NxN的矩阵绘制了每个人的友谊和仇恨,并用整数1表示友谊,用-1表示仇恨,用0表示纯粹的冷漠.
[[ 0, 1, 1, 1, 1], ? yes you like all your friends
[-1, 0, 1,-1, 0],
[-1, 1, 0, 1, 0],
[ 1, 1, 1, 0,-1],
[ 1, 0, 0,-1, 0]]
题:
- >编写一个Javascript方法,为给定的输入矩阵计算最佳座位排列作为数组,例如[0,4,2,1,3].(假设索引0和N-1相邻).解决方案的时间复杂度是多少？添加有关可能的优化的想法.
我已经尝试手动解决这个问题,但我不明白给定输入矩阵的问题示例[0,4,2,1,3].
有人可以启发我吗？
他/她是如何想出[0,4,2,1,3]的？
谢谢,非常感谢您的时间.