(ALGL4) Brute Force Techniques - II

Traveling Salesman Problem

#include <stdio.h>
#define N 4

int minDist = 100;
int totalDist = 0;
int graph[N][N] = {
	{0, 4, 2, 5},
	{3, 0, 1, 6},
	{4, 7, 0, 1},
	{4, 7, 9, 0},
};

void TSP(int path[], int visited[], int minPath[], int n)
{
	// exit case
	if (n == 0)
	{
		totalDist = 0;
		for (int i = 0; i < N - 1; i++)
			totalDist += graph[path[i]][path[i + 1]];
		totalDist += graph[path[N - 1]][path[0]]; // return to start

		// if the new total distance is the least we know, replace minDist/minPath
		if (totalDist < minDist)
		{
			minDist = totalDist;
			for (int i = 0; i < N; i++)
				minPath[i] = path[i];
		}

		return;
	}

	for (int i = 0; i < N; i++)
	{
		if (!visited[i])
		{
			path[n - 1] = i; // set as the last city in path???
			visited[i] = 1;	 // mark as visited

			TSP(path, visited, minPath, n - 1);

			visited[i] = 0; // mark as unvisited again
		}
	}
}

void main()
{
	int path[N], visited[N], minPath[N];

	for (int i = 0; i < N; i++)
	{
		path[i] = visited[i] = minPath[i] = 0; // initialize all to 0
	}

	TSP(path, visited, minPath, N);

	printf("\nMinimum distance: %d", minDist);
	printf("\nMinimum path: ");

	for (int i = 0; i < N; i++)
		printf("%d ", minPath[i] + 1);
	printf("\n");
}

Knapsack Problem

#include <stdio.h>
#define MAX 5

int result[MAX];
int maxProfit = 0;
int maxWeight = 10;

int sum(int arr[])
{
	int sum = 0;

	for (int i = 0; i < MAX; i++)
		sum += arr[i];

	return sum;
}

void knapsack(int values[], int weights[])
{
	int n = 1 << MAX;

	for (int i = 0; i < MAX; i++)
	{
		int k = 0;
		int testValues[MAX] = {0, 0, 0, 0, 0};
		int testWeights[MAX] = {0, 0, 0, 0, 0};

		for (int j = 0; j < MAX; j++)
		{
			if (i & (1 << j))
			{
				testValues[k] = values[j];
				testWeights[k] = weights[j];
				k++;
			}
		}

		if (sum(testValues) > maxProfit && sum(testWeights) <= maxWeight)
		{
			maxProfit = sum(testValues);
			for (int j = 0, k = 0; k < MAX; k++)
			{
				if (testValues[k])
				{
					result[j] = testValues[k];
					j++;
				}
			}
		}
	}
}

void main()
{
	int values[] = {2, 3, 4, 5, 6};
	int weights[] = {1, 3, 5, 6, 7};
	knapsack(values, weights);

	printf("\nMax Profit: %d", maxProfit);
	printf("\nChosen Values: ");

	int length = sizeof(result) / sizeof(result[0]);
	for (int i = 0; i < length; i++)
	{
		if (result[i] == 0)
		{
			break;
		}
		printf("%d ", result[i]);
	}
	printf("\n");
}

Job Assignment Problem

#include <stdio.h>
#define N 4

int minCost = 100;
int totalCost = 0;
int costs[N][N] = {
	{1, 4, 2, 5},
	{3, 2, 1, 6},
	{4, 7, 2, 1},
	{4, 7, 9, 2},
};

void jobAssignment(int workers[], int assigns[], int minAssigns[], int n)
{
	// exit case
	if (n == 0)
	{
		totalCost = 0;
		for (int i = 0; i < N; i++)
			totalCost += costs[i][workers[i]];

		if (totalCost < minCost)
		{
			minCost = totalCost;
			for (int i = 0; i < N; i++)
				minAssigns[i] = workers[i];
		}

		return;
	}

	for (int i = 0; i < N; i++)
	{
		if (!assigns[i])
		{
			workers[n - 1] = i;
			assigns[i] = 1;

			jobAssignment(workers, assigns, minAssigns, n - 1);

			assigns[i] = 0;
		}
	}
}

void main()
{
	int workers[N], assigns[N], minAssings[N];

	for (int i = 0; i < N; i++)
		workers[i] = assigns[i] = minAssings[i] = 0;

	jobAssignment(workers, assigns, minAssings, N);

	printf("\nMinimum cost: %d", minCost);
	printf("\nMinimum list: ");

	for (int i = 0; i < N; i++)
		printf("\n%d: %d", i + 1, minAssings[i] + 1);
	printf("\n");
}