https://www.acmicpc.net/problem/14889

Problem

N人をN/2人に分けて、それぞれのエネルギーの和を合わせた組み合わせの最高値の問題を探します.

Solution

1)グループ化
2)配列によるグループ化の組合せの解
3)テーブル内のグループ化されたコラボレーションの検索と追加
4)最大値を求める

Python Code

import sys
from itertools import combinations
from itertools import permutations
N=int(sys.stdin.readline())
NList=[i for i in range(1,N+1)]

arrList=[]

for _ in range(N):
    tmp=list(map(int,sys.stdin.readline().split()))
    arrList.append(tmp)
combiList=list(combinations(NList,N//2))

Asum=0
Bsum=0
minValue=1e9
def sumFunction(setRawPermu,setRemainPermu):
    global Asum
    global Bsum
    global minValue
    Asum=0
    Bsum=0


    for row in setRawPermu:

        Asum+=arrList[row[0]-1][row[1]-1]
    for row in setRemainPermu:
        Bsum+=arrList[row[0]-1][row[1]-1]
    minValue=min(minValue,abs(Asum-Bsum))

for combi in combiList:
    setRaw=list(combi)
    setRemain=list(set(NList)-set(setRaw))

    setRawPermu=list(permutations(setRaw,2))
    setRemainPermu=list(permutations(setRemain,2))
    sumFunction(setRawPermu,setRemainPermu)

print(minValue)