Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Please use Java and add comments for my understanding. Please don't copy and paste from old/similar answers - Clear instructions are provided. Thanks! 1.3 -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Please use Java and add comments for my understanding. Please don't copy and paste from old/similar answers - Clear instructions are provided. Thanks!
1.3
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
//BruteForce.java
import java.util.List; import java.util.ArrayList; import java.util.Arrays; public class BruteForce { public static void main(String args[]) { testOne(); // testTwo(); } //--------------------------------------------------- // An example, with four friends: Jack, Mary, Henry, and Elizabeth // - Jack has a conflict with Mary and Elizabeth // - Mary has conflict with Henry and Elizabeth // - Henry has a conflict with Elizabeth // There is a single subset of size = 2 having no conflicts: // Jack and Henry public static void testOne() { Friend jack = new Friend("Jack"); Friend mary = new Friend("Mary"); Friend henry = new Friend("Henry"); Friend elizabeth = new Friend("Elizabeth"); Friend[] allFriends = {jack, mary, henry, elizabeth}; Friend[] jack_conflicts = {mary, elizabeth}; jack.setConflicts(new ArrayList(Arrays.asList(jack_conflicts))); Friend[] mary_conflicts = {henry, elizabeth}; mary.setConflicts(new ArrayList (Arrays.asList(mary_conflicts))); Friend[] henry_conflicts = {elizabeth}; henry.setConflicts(new ArrayList (Arrays.asList(henry_conflicts))); List best = optimize(allFriends); System.out.println("largest independent set:"); for (Friend f: best) System.out.print(f + " "); System.out.println(); } //--------------------------------------------------- public static void testTwo() { // implement this List best = optimize(allFriends); System.out.println("largest independent set:"); for (Friend f: best) System.out.print(f + " "); System.out.println(); } //---------------------------------------------------------- public static List optimize(Friend allFriends[]) { // implement this } // optimize() } ---------------------------------------------------------------------------------------------------------------------------------------------
//Friend.java import java.util.List; import java.util.ArrayList; public class Friend { String name; List1 Independent Sets You have ten friends. Some of them have conflicts with each other. You want to invite as many friends as you can to a dinner party, in a way that none of your guests has a conflict with any other guest. We will assume that "has conflict with" is a symmetric relationship: if A has a conflict with B, then B also has a conflict with A. (And no person has a self-conflict.) 1.1 List of friends Here is a table showing your friends and showing which friends have conflicts with other friends: Since the "has conflict with" relation is symmetric, the table itself is symmetric. Find the maximal independent set: the largest set of friends such that no friend in the set has a conflict with any other friend in the set. I've created infrastructure for you, in the BruteForce folder of the BruteForce.java and Friend. java. Use these. 1.2 Enumerating subsets Here's an easy way to enumerate all of the subsets of a given set: suppose I have N items in my set. Declare a boolean array choose [] of size N. Then, do the following: for index =0 to 2N1{ for j=0 to N1{ choose [j]= false \} for j=0 to N1{ if bit j of index is set \{ 1 choose [j]= true \} // now, build the ith subset of the friends: // for j in 0 to N1, include friend j if choose[j] is true // if there are no conflicts among the friends chosen in this set, // then count how many friends are in this set // keep track of the largest subset seen \} Here's how to determine if the ith bit of index is set (0iconflicts; public Friend(String name) { this.name = name; this.conflicts = new ArrayList (); } public String toString() { return this.name; } public void setConflicts(List conflicts) { for (Friend friend: conflicts) this.conflicts.add(friend); } public boolean hasConflictWith(Friend friend) { int idx = this.conflicts.indexOf(friend); if (idx >= 0) return true; else return false; } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started