Backtracking – Apartments

An algortithm with apartments persons repartisation:

#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<values.h>

#define MAX_APART 20

int n;  //nr persoane
int pref[MAX_APART][MAX_APART];//preferinta pers i pt apart j
int take[MAX_APART];//apart repartizat persoanei i
int best_take[MAX_APART];//alegerea cea mai buna a apartam
int best_satisfaction;
int exit_sol;//daca avem sau nu o solutie

void read_data()
{
	int i,j;

	printf("Nr apartamente= ");scanf("%d",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			printf("Optiunea persoanei %d pt apart. %d este ",i,j);
			scanf("%d",&pref[i][j]);
		}
		best_satisfaction = MAXINT;
}

void final(int optim)
{
	int i;

	exit_sol = true;
	best_satisfaction = optim;
	for(i=1;i<=n;i++)
		best_take[i] = take[i];
}

int canContinue(int k,int optim)
{
	int i;
	for(i=1;i<k;i++)
		if(take[k] = take[i])
			return false;
	if(optim + pref[k][take[k]] > best_satisfaction)
		return false;
	return true;
}

void back(int persoana,int optim)
{
	if(persoana == n+1)
		final(optim);
	else
	{
		take[persoana] = 0;
		while(take[persoana] + 1 <= n)
		{
			take[persoana]++;
			if(canContinue(persoana,optim))
				back(persoana+1,optim+pref[persoana][take[persoana]]);
		}
	}
}

void main()
{
	int i;

	read_data();
	exit_sol = false;
	back(1,0);
	if(!exit_sol)
		printf("Nu avem solutie! \n");
	else
	{
		for(i=1;i<=n;i++)
			printf("Persoana %d va lua apartamentul %d. \n",i,best_take[i]);
	}
}

25,356 total views, 1 views today