Share

# 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

{
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;

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]);
}
}```

8,782 total views, 23 views today

Posted In: