矩阵取值优化算法

已知一个N*N的矩阵A，N为偶数，要从A中取出N/2个元素保证它们的和是最小的，限制条件是
  

（1）主对角线元素不可取
  

（2）如果选取了A中的第i行第j列的元素aij，那么aji（第j行第i列的元素）就不能选了。
  

N值较大，希望高手能给出比较快的算法。