This problem can be solved with bit DP (Dynamic Programming).

Definition of state

Let us define \(\mathrm{dp}[b]\) by

• the maximum total weight of the chosen edges when, for each vertex \(i_1,i_2,\ldots,i_k\), an edge that is connected to the vertex is chosen, or such an edge is determined not to be chosen, where \(i_1,i_2,\ldots,i_k\) is the bits of \(b\) that are set.

The answer is \(\mathrm{dp}[2^N-1]\).

Transitions

We evaluate \(\mathrm{dp}[b]\) in ascending order of \(b\). A transition from a state is done by inspecting all edges to be added next and checking if both endpoints of the edge is not contained in \(b\). One can focus on the vertex with the minimum index not contained in \(b\) to improve the complexity. The sample code adopts this approach.

• Sample code (C++)

#include <bits/stdc++.h>
using namespace std;

#define rep(i, x) for(int i = 0; i < (x); i++)

int main() {
	int n;
	cin >> n;
	vector d(n, vector(n, 0));
	rep(i, n) {
		for(int j = i + 1; j < n; j++) cin >> d[i][j];
	}
	vector dp(1 << n, 0ll);
	rep(b, (1 << n) - 1) {
		int l = -1;
		rep(i, n) if(!(b >> i & 1)) {
			l = i;
			break;
		}
		rep(i, n) if(!(b >> i & 1)) {
			int nb = b | (1 << l) | (1 << i);
			dp[nb] = max(dp[nb], dp[b] + d[l][i]);
		}
	}
	cout << dp.back() << endl;
}