Exhaustive Search Algorithm:
Exhaustive Search is a brute-force algorithm that systematically enumerates all possible solutions to a problem and checks each one to see if it is a valid solution. This algorithm is typically used for problems that have a small and well-defined search space, where it is feasible to check all possible solutions.
Examples:
Input: Items[] = {1, 2, 3, 4, 5, 6};
List of sets = {1, 2, 3}, {4, 5}, {5, 6}, {1, 4}
Output: Maximum number of sets that can be packed: 3Input: Items[] = {1, 2};
List of sets = {1}, {4, }, {5}, {1}
Output: Maximum number of sets that can be packed: 1
Approach:
Loop through all the sets and check if the current item is in the current set If the item is in the set, increment the number of sets that can be packed and Update the maximum number of sets that can be packed
Here is a step-by-step description of how the algorithm works in this code:
- The program defines a maxPackedSets() function that takes a set of items and a list of sets as input.
- The function initializes the maximum number of sets that can be packed to 0.
- The function loops through all the sets in the list of sets. For each set, it initializes the number of sets that can be packed to 0.
- The function then loops through all the items in the set of items. For each item, it checks if the item is in the current set. If the item is in the set, the number of sets that can be packed is incremented and the item is removed from the set of items so that it is not counted again.
- The function then updates the maximum number of sets that can be packed by taking the maximum of the current maximum and the number of sets that can be packed for the current set.
- The function repeats steps 3-5 for all the sets in the list of sets.
- Once all the sets have been processed, the function returns the maximum number of sets that can be packed as the result.
- The main() function of the program creates a set of items and a list of sets and then calls the maxPackedSets() function to find the maximum number of sets that can be packed into the given set of items.
- The result of the maxPackedSets() function is printed to the console, indicating the maximum number of sets that can be packed.
Thus, the code uses the Exhaustive Search algorithm to systematically enumerate and check all the sets in the list of sets to find the maximum number of sets that can be packed into the given set of items. This is a simple and straightforward approach to solving the Set Packing problem, but it can be slow and computationally expensive for problems with a large search space.
Here is a Java program that implements the Exhaustive Search algorithm for the Set Packing problem:
C++
#include <bits/stdc++.h>using namespace std;int maxPackedSets(vector<int>& items, vector<set<int> >& sets){ // Initialize the maximum number of sets that can be // packed to 0 int maxSets = 0; // Loop through all the sets for (auto set : sets) { // Initialize the number of sets that can be packed // to 0 int numSets = 0; // Loop through all the items for (auto item : items) { // Check if the current item is in the current // set if (set.count(item)) { // If the item is in the set, increment // the number of sets that can be packed numSets += 1; // Remove the item from the set of items, // so that it is not counted again items.erase(remove(items.begin(), items.end(), item), items.end()); } } // Update the maximum number of sets that can be // packed maxSets = max(maxSets, numSets+1); } return maxSets;}int main(){ // Set of items vector<int> items = { 1, 2, 3, 4, 5, 6 }; // List of sets vector<set<int> > sets = { { 1, 2, 3 }, { 4, 5 }, { 5, 6 }, { 1, 4 } }; // Find the maximum number of sets that // can be packed into the given set of items int maxSets = maxPackedSets(items, sets); // Print the result cout << "Maximum number of sets that can be packed: " << maxSets << endl; return 0;}// This code is contributed by poojaagarwal2. |
Java
// Package whatever// do not write package name hereimport java.io.*;import java.util.ArrayList;import java.util.List;public class SetPacking { // Function to find the maximum number // of sets that can be packed into the // given set of items public static int maxPackedSets(int[] items, List<int[]> sets) { // Initialize the maximum number of // sets that can be packed to 0 int maxSets = 0; // Loop through all the sets for (int[] set : sets) { // Initialize the number of sets // that can be packed to 0 int numSets = 0; // Loop through all the items for (int item : items) { // Check if the current item // is in the current set if (contains(set, item)) { // If the item is in the // set, increment the // number of sets that // can be packed numSets++; // Remove the item from // the set of items, so // that it is not counted again items = remove(items, item); } } // Update the maximum number // of sets that can be packed maxSets = Math.max(maxSets, numSets); } return maxSets; } // Function to check if an array // contains a given value public static boolean contains(int[] array, int value) { for (int element : array) { if (element == value) { return true; } } return false; } // Function to remove a given // value from an array public static int[] remove(int[] array, int value) { List<Integer> result = new ArrayList<>(); for (int element : array) { if (element != value) { result.add(element); } } return result.stream().mapToInt(i -> i).toArray(); } public static void main(String[] args) { // Set of items int[] items = { 1, 2, 3, 4, 5, 6 }; // List of sets List<int[]> sets = new ArrayList<>(); sets.add(new int[] { 1, 2, 3 }); sets.add(new int[] { 4, 5 }); sets.add(new int[] { 5, 6 }); sets.add(new int[] { 1, 4 }); // Find the maximum number of sets // that can be packed into the // given set of items int maxSets = maxPackedSets(items, sets); // Print the result System.out.println( "Maximum number of sets that can be packed: " + maxSets); }} |
Python3
# Python code for the above approachdef maxPackedSets(items, sets): # Initialize the maximum number of sets that can be packed to 0 maxSets = 0 # Loop through all the sets for set in sets: # Initialize the number of sets that can be packed to 0 numSets = 0 # Loop through all the items for item in items: # Check if the current item is in the current set if item in set: # If the item is in the set, increment # the number of sets that can be packed numSets += 1 # Remove the item from the set of items, # so that it is not counted again items = [i for i in items if i != item] # Update the maximum number of sets that can be packed maxSets = max(maxSets, numSets) return maxSets# Set of itemsitems = [1, 2, 3, 4, 5, 6]# List of setssets = [ [1, 2, 3], [4, 5], [5, 6], [1, 4]]# Find the maximum number of sets that# can be packed into the given set of itemsmaxSets = maxPackedSets(items, sets)# Print the resultprint(f"Maximum number of sets that can be packed: {maxSets}")# This code is contributed by Potta Lokesh |
C#
// C# code implementation:using System;using System.Linq;using System.Collections.Generic;public class GFG { // Function to find the maximum number // of sets that can be packed into the // given set of items public static int MaxPackedSets(int[] items, List<int[]> sets) { // Initialize the maximum number of // sets that can be packed to 0 int maxSets = 0; // Loop through all the sets foreach(int[] set in sets) { // Initialize the number of sets // that can be packed to 0 int numSets = 0; // Loop through all the items foreach(int item in items) { // Check if the current item // is in the current set if (Contains(set, item)) { // If the item is in the // set, increment the // number of sets that // can be packed numSets++; // Remove the item from // the set of items, so // that it is not counted again items = Remove(items, item); } } // Update the maximum number // of sets that can be packed maxSets = Math.Max(maxSets, numSets); } return maxSets; } // Function to check if an array // contains a given value public static bool Contains(int[] array, int value) { foreach(int element in array) { if (element == value) { return true; } } return false; } // Function to remove a given // value from an array public static int[] Remove(int[] array, int value) { List<int> result = new List<int>(); foreach(int element in array) { if (element != value) { result.Add(element); } } return result.ToArray(); } static public void Main() { // Code // Set of items int[] items = { 1, 2, 3, 4, 5, 6 }; // List of sets List<int[]> sets = new List<int[]>(); sets.Add(new int[] { 1, 2, 3 }); sets.Add(new int[] { 4, 5 }); sets.Add(new int[] { 5, 6 }); sets.Add(new int[] { 1, 4 }); // Find the maximum number of sets // that can be packed into the // given set of items int maxSets = MaxPackedSets(items, sets); // Print the result Console.WriteLine( "Maximum number of sets that can be packed: " + maxSets); }}// This code is contributed by lokesh. |
Javascript
function maxPackedSets(items, sets) { // Initialize the maximum number of sets that can be packed to 0 let maxSets = 0; // Loop through all the sets for (let set of sets) { // Initialize the number of sets that can be packed to 0 let numSets = 0; // Loop through all the items for (let item of items) { // Check if the current item is in the current set if (set.includes(item)) { // If the item is in the set, increment the number of sets that can be packed numSets++; // Remove the item from the set of items, so that it is not counted again items = items.filter(i => i !== item); } } // Update the maximum number of sets that can be packed maxSets = Math.max(maxSets, numSets); } return maxSets;}// Set of itemslet items = [1, 2, 3, 4, 5, 6];// List of setslet sets = [ [1, 2, 3], [4, 5], [5, 6], [1, 4]];// Find the maximum number of sets that can be packed into the given set of itemslet maxSets = maxPackedSets(items, sets);// Print the resultconsole.log(`Maximum number of sets that can be packed: ${maxSets}`); |
Output
Maximum number of sets that can be packed: 3
Characteristics of Exhaustive Search Algorithm:
- The Exhaustive Search algorithm is a simple and straightforward approach to solving problems.
- However, it can be slow and computationally expensive, especially for problems with a large search space.
- It is also not guaranteed to find the optimal solution to a problem, as it only checks solutions that are explicitly enumerated by the algorithm.
- Despite these limitations, Exhaustive Search can be a useful technique for solving certain types of problems.
Complexity Analysis:
Time Complexity: The complexity of the maxPackedSets function is O(nm) where n is the length of the items array and m is the number of sets in the sets list. This is because the function loops through all the items (n) and all the sets (m) in two separate loops.
- The complexity of the contains function is O(n) because it loops through all the elements in the array (n).
- The complexity of the remove function is O(n) because it loops through all the elements in the array (n) and adds them to a new list if they are not the value to be removed.
- Overall, the complexity of the entire program is O(n*m)
Auxiliary Space: O(n*m)
The space complexity of the maxPackedSets function is O(nm) because it creates a new list for the result of the remove function for each item in the items array and each set in the sets list.
- The space complexity of the contains function is O(1) because it only uses a fixed number of variables regardless of the size of the input.
- The space complexity of the remove function is O(n) because it creates a new list with a size equal to the number of elements in the input array that are not the value to be removed.
- Overall, the space complexity of the entire program is O(n*m)
