From 9920a766c17402a58fc4457d2fc643cc7905e684 Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Mon, 11 Jun 2018 16:46:43 +0800
Subject: 112, 345-347

---
 euler345.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 67 insertions(+)
 create mode 100644 euler345.c

(limited to 'euler345.c')

diff --git a/euler345.c b/euler345.c
new file mode 100644
index 0000000..b598981
--- /dev/null
+++ b/euler345.c
@@ -0,0 +1,67 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+int mxsum(int **m, int n, int d, int visited[])
+{
+	int ans;
+	int sel = -1;
+	if (d == n)
+		return 0;
+
+	/* select the biggest of the line first */
+	for (int i = 0; i < n; i++) {
+		if (!visited[i]) {
+			if (sel == -1)
+				sel = i;
+			else if (m[d][i] > m[d][sel])
+				sel = i;
+		}
+	}
+	visited[sel] = 1;
+	ans = m[d][sel] + mxsum(m, n, d+1, visited);
+	visited[sel] = 0;
+
+	for (int i = 0; i < n; i++) {
+		if (visited[i] || i == sel)
+			continue;
+		visited[i] = 1;
+		int t = m[d][i];
+		/* estimate the maximum value of remaining numbers */
+		int re = 0;
+		for (int j = d+1; j < n; j++) {
+			int linemax = 0;
+			for (int k = 0; k < n; k++) {
+				if (!visited[k] && m[j][k] > linemax)
+					linemax = m[j][k];
+			}
+			re += linemax;
+		}
+		if (t + re > ans) {
+			t += mxsum(m, n, d+1, visited);
+		}
+		visited[i] = 0;
+		if (t > ans)
+			ans = t;
+	}
+	return ans;
+}
+
+int main()
+{
+	int n;
+	int **m;
+	int visited[15];
+
+	scanf("%d", &n);
+	m = (int**)malloc(sizeof(int*) * n);
+	memset(visited, 0, sizeof(visited));
+	for (int i = 0; i < n; i++) {
+		m[i] = (int*)malloc(sizeof(int) * n);
+		for (int j = 0; j < n; j++) {
+			scanf("%d", &m[i][j]);
+		}
+	}
+
+	printf("%d\n", mxsum(m, n, 0, visited));
+}
-- 
cgit v1.2.3