Answer to Question #284082 in C++ for Umar

Question

Write a c++ program to divide 20 rooms to 30 employees using greedy algorithms such as knapsack method using Structured programming

Answer 1

// C++ program for activity selection problem.

// The following implementation assumes that the activities

// are already sorted according to their finish time

#include <bits/stdc++.h>

using namespace std;

 

// Prints a maximum set of activities that can be done by a single

// person, one at a time.

//  n   -->  Total number of activities

//  s[] -->  An array that contains start time of all activities

//  f[] -->  An array that contains finish time of all activities

void printMaxActivities(int s[], int f[], int n)

{

    int i, j;

 

    cout <<"Following activities are selected "<< endl;

 

    // The first activity always gets selected

    i = 0;

    cout <<" "<< i;

 

    // Consider rest of the activities

    for (j = 1; j < n; j++)

    {

      // If this activity has start time greater than or

      // equal to the finish time of previously selected

      // activity, then select it

      if (s[j] >= f[i])

      {

          cout <<" " << j;

          i = j;

      }

    }

}

 

// driver program to test above function

int main()

{

    int s[] =  {1, 3, 0, 5, 8, 5};

    int f[] =  {2, 4, 6, 7, 9, 9};

    int n = sizeof(s)/sizeof(s[0]);

    printMaxActivities(s, f, n);

    return 0;

}

//this code contributed by shivanisinghss2110







C























// C program for activity selection problem.

// The following implementation assumes that the activities

// are already sorted according to their finish time

#include<stdio.h>

 

// Prints a maximum set of activities that can be done by a single

// person, one at a time.

//  n   -->  Total number of activities

//  s[] -->  An array that contains start time of all activities

//  f[] -->  An array that contains finish time of all activities

void printMaxActivities(int s[], int f[], int n)

{

    int i, j;

 

    printf ("Following activities are selected n");

 

    // The first activity always gets selected

    i = 0;

    printf("%d ", i);

 

    // Consider rest of the activities

    for (j = 1; j < n; j++)

    {

      // If this activity has start time greater than or

      // equal to the finish time of previously selected

      // activity, then select it

      if (s[j] >= f[i])

      {

          printf ("%d ", j);

          i = j;

      }

    }

}

 

// driver program to test above function

int main()

{

    int s[] =  {1, 3, 0, 5, 8, 5};

    int f[] =  {2, 4, 6, 7, 9, 9};

    int n = sizeof(s)/sizeof(s[0]);

    printMaxActivities(s, f, n);

    return 0;

}








Java























// The following implementation assumes that the activities

// are already sorted according to their finish time

import java.util.*;

import java.lang.*;

import java.io.*;

 

class ActivitySelection

{

    // Prints a maximum set of activities that can be done by a single

    // person, one at a time.

    //  n   -->  Total number of activities

    //  s[] -->  An array that contains start time of all activities

    //  f[] -->  An array that contains finish time of all activities

    public static void printMaxActivities(int s[], int f[], int n)

    {

    int i, j;

      

    System.out.print("Following activities are selected : n");

      

    // The first activity always gets selected

    i = 0;

    System.out.print(i+" ");

      

    // Consider rest of the activities

    for (j = 1; j < n; j++)

    {

         // If this activity has start time greater than or

         // equal to the finish time of previously selected

         // activity, then select it

         if (s[j] >= f[i])

         {

              System.out.print(j+" ");

              i = j;

          }

     }

    }

      

    // driver program to test above function

    public static void main(String[] args)

    {

    int s[] =  {1, 3, 0, 5, 8, 5};

    int f[] =  {2, 4, 6, 7, 9, 9};

    int n = s.length;

        

    printMaxActivities(s, f, n);

    }

     

}