Question

In: Computer Science

Java problem Given the uncertainty surrounding the outbreak of the Coronavirus disease (COVID-19) pandemic, our federal...

Java problem

Given the uncertainty surrounding the outbreak of the Coronavirus disease (COVID-19) pandemic, our federal government has to work tirelessly to ensure the distribution of needed resources such as medical essentials, water, food supply among the states, townships, and counties in the time of crisis.

You are a software engineer from the Right Resource, a company that delivers logistic solutions to local and state entities (schools, institutions, government offices, etc). You are working on a software solution to check that given a set of resources, whether they can be proportioned and distributed equally to k medical facilities. Resources are represented as an array of positive integers. You want to see if these resources can be sub-divided into k facilities, each having the same total sum (of resources) as the other facilities. For example with resources = {1,2,3,4,5,6} we can sub-divide them into k = 3 medical facilities, each having the same total sum of 7: {1,6}, {2,5}, and {3,4}.

STARTER CODE

Write a solution method, canDistribute, that returns whether it is possible (true or false) that a given set of resources divides into k equal-sum facilities. You will solve this problem using a recursion:

public class HomeworkAssignment5_2 {    
   public static void main(String[] args) {
      // just like any problems, whatever you need here, etc.
   }
}
class Solution {
   // YOUR STYLING DOCUMENTATION GOES HERE
   public boolean canDistribute(int[] resources, int groups) { 
      // YOUR CODE HERE 
   }
}

EXAMPLES

input: {3,4,5,6}, 2

output: true

Explanation: {3,6}, {4,5}

input: {1}, 1

output: true

Explanation: {1}

input: {1, 3, 2, 3, 4, 1, 3, 5, 2, 1}, 5

output: true

Explanation: {3,2}, {4,1}, {5}, {2,3}, {1,3,1}

input: {1}, 4

output: false

Explanation: cannot split further with a value of 1 in resource.

CONSTRAINTS / ASSUMPTIONS

  • 0 < resources.length() < 1000.
  • 0 < medical facilities < 1000.
  • A sub-divided facility is never empty.
  • The solution method returns false if resources cannot be evenly distributed, true otherwise.
  • There may be more than one ways to sub-divide a given set of resources into k facilities. Doesn't matter. Your solution should return true in that case.
  • You will use a Recursion for this. Failure to do so received -4 points.

HINT

  • Note: you may choose to solve this problem in your own way or use the following pseudo code.
  • Check for all boundary conditions to return result immediately if known, e.g., resources.length() = 1 and k = 1, return true, resources.length() = 1 and k = 4, return false, etc.
  • Find the purported allocation for each group, i.e., allocation = SUM(resources)/k.
  • Sort the resources in either ascending or descending order.
  • Create another solution method of your choice to enable recursion.
  • Remaining Pseudo Code:
    1. Create an empty array of integers with k elements. This is your "memory buffer". At the end of your recursion, you want this memory buffer be filled with equally allocated values, allocation.
    2. Pick the highest resource (one with the highest integral value) in your resources.
    3. Check if the selected resource is <= allocation:
      • If yes, add that value to the first available element in your memory buffer of k elements. Go to #4.
      • If not, move on to other elements in your memory buffer to see if there's available space to accommodate it.
      • If there's no available space to accommodate the selected resource, it is impossible for resources to be allocated equally.
    4. Advance to the next highest resource. Repeat Step #3. If all resources have been considered and there is no more next highest, go to Step #5.
    5. Check if every element in your memory buffer has the same value. If so you have an evenly allocated distribution - return true. False otherwise.

Solutions

Expert Solution

import java.util.Scanner;
class Solution
{
    static boolean isKPartitionPossibleRec(int arr[], int subsetSum[], boolean taken[], 
                int subset, int K, int N, int curIdx, int limitIdx) 
{ 
    if (subsetSum[curIdx] == subset) 
    { 
        /* current index (K - 2) represents (K - 1) subsets of equal 
            sum last partition will already remain with sum 'subset'*/
        if (curIdx == K - 2) 
            return true; 
  
        // recursive call for next subsetition 
        return isKPartitionPossibleRec(arr, subsetSum, taken, subset, 
                                            K, N, curIdx + 1, N - 1); 
    } 
  
    // start from limitIdx and include elements into current partition 
    for (int i = limitIdx; i >= 0; i--) 
    { 
        // if already taken, continue 
        if (taken[i]) 
            continue; 
        int tmp = subsetSum[curIdx] + arr[i]; 
  
        // if temp is less than subset then only include the element 
        // and call recursively 
        if (tmp <= subset) 
        { 
            // mark the element and include into current partition sum 
            taken[i] = true; 
            subsetSum[curIdx] += arr[i]; 
            boolean nxt = isKPartitionPossibleRec(arr, subsetSum, taken, 
                                            subset, K, N, curIdx, i - 1); 
  
            // after recursive call unmark the element and remove from 
            // subsetition sum 
            taken[i] = false; 
            subsetSum[curIdx] -= arr[i]; 
            if (nxt) 
                return true; 
        } 
    } 
    return false; 
} 
  
// Method returns true if arr can be partitioned into K subsets 
// with equal sum 
static boolean canDistribute(int arr[], int K) 
{ 
    int N=arr.length;
    // If K is 1, then complete array will be our answer 
    if (K == 1) 
        return true; 
  
    // If total number of partitions are more than N, then 
    // division is not possible 
    if (N < K) 
        return false; 
  
    // if array sum is not divisible by K then we can't divide 
    // array into K partitions 
    int sum = 0; 
    for (int i = 0; i < N; i++) 
        sum += arr[i]; 
    if (sum % K != 0) 
        return false; 
  
    // the sum of each subset should be subset (= sum / K) 
    int subset = sum / K; 
    int []subsetSum = new int[K]; 
    boolean []taken = new boolean[N]; 
  
    // Initialize sum of each subset from 0 
    for (int i = 0; i < K; i++) 
        subsetSum[i] = 0; 
  
    // mark all elements as not taken 
    for (int i = 0; i < N; i++) 
        taken[i] = false; 
  
    // initialize first subsubset sum as last element of 
    // array and mark that as taken 
    subsetSum[0] = arr[N - 1]; 
    taken[N - 1] = true; 
  
    // call recursive method to check K-substitution condition 
    return isKPartitionPossibleRec(arr, subsetSum, taken, 
                                    subset, K, N, 0, N - 1); 
}
}
class HomeworkAssignment5_2 
{
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("Please neter size of array");
        int size=sc.nextInt();
        int res[]=new int[size];
        for(int i=0;i<size;i++)
        {
            res[i]=sc.nextInt();
        }
        System.out.println("Please enter value of k");
        int k=sc.nextInt();
        
        Solution obj=new Solution();
        if(obj.canDistribute(res,k))
        System.out.println("true");
        else
        System.out.println("false");
        
    }
    
}

Here is the desired code. I hope it helps.


Related Solutions

This program should be written in Java language. Given the uncertainty surrounding the outbreak of the...
This program should be written in Java language. Given the uncertainty surrounding the outbreak of the Coronavirus disease (COVID-19) pandemic, our federal government has to work tirelessly to ensure the distribution of needed resources such as medical essentials, water, food supply among the states, townships, and counties in the time of crisis. You are a software engineer from the Right Resource, a company that delivers logistic solutions to local and state entities (schools, institutions, government offices, etc). You are working...
a) Has globalization ended with the coronavirus (Kovid-19) pandemic? How will this coronavirus outbreak crisis affect...
a) Has globalization ended with the coronavirus (Kovid-19) pandemic? How will this coronavirus outbreak crisis affect the international financial system? Please explain minimum 3 pages
During the outbreak of Coronavirus (COVID-19), is the market for taxi rides at the equilibrium? Is...
During the outbreak of Coronavirus (COVID-19), is the market for taxi rides at the equilibrium? Is the market efficient? Is the market fair? Explain with a diagram
By now, you know all bout CORONAVIRUS (COVID-19) as a pandemic threat to the world. COVID-19...
By now, you know all bout CORONAVIRUS (COVID-19) as a pandemic threat to the world. COVID-19 has and will have stressful effects on all of us--individually, family,socially, culturally, nationally, economically, technologically, and what not. Given the stressful and dangerous threat, what do you think COVID-19 will have on ECONOMIC manager's decisions--segmentation, product decisions, promotional activities, pricing, supply chain (distribution), and customer relationships. You can use any company that you are familiar with, including the ones you have worked for in...
COVID-19 is a contagious disease caused by a newly discovered coronavirus.
  PHC231 COVID-19 is a contagious disease caused by a newly discovered coronavirus. It is an ongoing health emergency globally, and the risk of hospital-acquired infection is worrying about health workers. In this situation, discuss the epidemiological aspects of disease transmission and the types of prevention and control methods that should be taken to restrict or minimize the spread of infection in a healthcare setting. How much of a current threat do you feel this outbreak has on the population...
The presence of Corona Virus Disease 2019 (COVID-19) in Malaysia, is part of the COVID-19 pandemic,...
The presence of Corona Virus Disease 2019 (COVID-19) in Malaysia, is part of the COVID-19 pandemic, was first reported in January 2020. Due to that, Malaysia Movement Control (MCO) is a cordon sanitaire implemented as a preventive measure by the federal government of Malaysia in response to the COVID-19 pandemic in the country on 18 March 2020. The order was commonly referred to in local and international media as a "lockdown". As a University student in network especially in wireless...
Explain how the outbreak of the COVID-19 pandemic impacts on the accounting information system as a...
Explain how the outbreak of the COVID-19 pandemic impacts on the accounting information system as a natural disaster and the strategies businesses can adopt to maintain current business operations
c) Discuss if the recent outbreak of the Covid-19 pandemic will mark the end of globalisation?...
c) Discuss if the recent outbreak of the Covid-19 pandemic will mark the end of globalisation?
Following the outbreak of the Novel Coronavirus (COVID 19), CPC a pharmaceutical company is considering introducing...
Following the outbreak of the Novel Coronavirus (COVID 19), CPC a pharmaceutical company is considering introducing a new vaccine unto the market to help fight the virus. This will require the injection of huge capital to the tune of GH¢40,000,000 for the purchase of the equipment for production. It will cost CPC an additional GH¢ 5,500,000 to set up the production facility and install that equipment for production. Mr. Smart, the CEO of CPC believes that the vaccine could be...
Following the outbreak of the Novel Coronavirus (COVID 19), CPC a pharmaceutical company is considering introducing...
Following the outbreak of the Novel Coronavirus (COVID 19), CPC a pharmaceutical company is considering introducing a new vaccine unto the market to help fight the virus. This will require the injection of huge capital to the tune of GH¢40,000,000 for the purchase of the equipment for production. It will cost CPC an additional GH¢ 5,500,000 to set up the production facility and install that equipment for production. Mr. Smart, the CEO of CPC believes that the vaccine could be...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT