🔗 Budget

Company S conducted a survey to find out how much money each department needs to purchase supplies, in order to support each department. However, since the total budget is fixed, it's not possible to buy supplies for every department. So the company wants to support as many departments as possible.

When supporting a department, it must be given exactly the amount it requested. For example, a department that requested 1,000 won must receive exactly 1,000 won — it cannot be given less than that.

Given an array d containing the amounts requested by each department, and a budget parameter, complete the solution function to return the maximum number of departments that can be supported.

• d is an array containing the amounts requested by each department, and its length (the total number of departments) is between 1 and 100.
• Each element of d represents the amount requested by a department, which is a natural number between 1 and 100,000.
• budget represents the total budget, a natural number between 1 and 10,000,000.

Example #1

Each department requested [1 won, 3 won, 2 won, 5 won, 4 won]. If we buy supplies for the departments that requested 1 won, 2 won, and 4 won, 7 won out of the 9 won budget is spent, leaving 2 won. Since departments must always be given exactly the amount they requested, the remaining 2 won cannot be used to support any other department. Besides this method, there are other ways to support 3 departments:

• Supporting the departments that requested 1 won, 2 won, and 3 won requires 6 won.
• Supporting the departments that requested 1 won, 2 won, and 5 won requires 8 won.
• Supporting the departments that requested 1 won, 3 won, and 4 won requires 8 won.
• Supporting the departments that requested 1 won, 3 won, and 5 won requires 9 won.

Since it's not possible to support more than 3 departments, the maximum number of departments that can be supported is 3.

Example #2

Buying supplies for every department costs 10 won. So a maximum of 4 departments can be supported.

With a bit of thought, this isn't too hard. The goal is to allocate the budget to as many departments as possible, and for each department you either give the full amount or nothing at all — you can't give half or a partial amount.

There's no need to overthink it — sort by requested amount, and count departments in order starting from the one that requested the least.

Since the budget is limited, giving it out in order from the smallest request increases the chance of supporting more departments.

1. Sort by requested amount
2. Subtract the requested amount from the budget until it goes below 0

The moment it drops below 0, the budget has been exceeded, so from that department onward, no more support can be given.

JAVA
import java.util.Arrays;

/**
 * Budget class
 *
 * @author RWB
 * @since 2021.12.12 Sun 03:07:33
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param d: [int[]] amount requested by each department
	 * @param budget: [int] budget
	 *
	 * @return [int] answer
	 */
	public int solution(int[] d, int budget)
	{
		int answer = 0;
		
		Arrays.sort(d);
		
		for (int j : d)
		{
			budget -= j;
			
			// If the budget is exceeded
			if (budget < 0)
			{
				break;
			}
			
			answer++;
		}
		
		return answer;
	}
}