Question

I have a below codes with all details and need to answer this below question ONLY!

How to explain below codes with the two properties of a Greedy algorithm - Optimal Substructure and the Greedy Property line by line?

======================

public class TeamFormation
{
private static ArrayList buildTeam(ArrayList team, int skill)
{
ArrayList newTeam = new ArrayList();
newTeam.add(skill);
for (int player : team)
{
if (skill == (player + 1))
{
newTeam.add(player);
}
}
return newTeam;
}
private static boolean canBuildTeam(ArrayList team, int skill)
{
boolean canBuildTeam = false;
for (int player : team)
{
if (skill == (player + 1))
{
canBuildTeam = true;
break;
}
}
return canBuildTeam;
}
private static void printSmallestTeam(ArrayList> teams)
{
int tmp;
int smallest = teams.get(0).size();
for (int i = 1; i < teams.size(); ++i)
{
tmp = teams.get(i).size();
if (tmp < smallest)
{
smallest = tmp;
}
}
System.out.println(smallest);
}
private static void findSmallestTeam(ArrayList team)
{
ArrayList> teams = new ArrayList>();
for (int player : team)
{
if (canBuildTeam(team, player))
{
teams.add(buildTeam(team, player));
}
}
printSmallestTeam(teams);
}
public static void main(String[] args)
{
int i, n, t;
Scanner scanner = new Scanner(System.in);
ArrayList team = new ArrayList();
t = scanner.nextInt();
while (t > 0)
{
n = scanner.nextInt();
for (i = 0; i < n; ++i)
{
team.add(scanner.nextInt());
}
findSmallestTeam(team);
--t;
}
scanner.close();
}

}

Answer 1

In the above code, we need to find the smallest team. Greedy approach makes the decisions based on the locally optimal solution to get global optimal solution. So it checks whether we can form a team with the current value or team player or not and if it is true then adds it to the team. There may be a better optimal solution if we take other values by searching further but since it is greedy it just considers the current value and takes decision. We need not update or form team every time we encounter a value, it is already stored. This property shows optimal substructure property.