🔗 Budget

In order to support each department with the items it needs, company S surveyed the amount of money each department needs to purchase its items. However, since the total budget is fixed, it's not possible to buy items for every department. So the goal is to support as many departments as possible.

When purchasing items for a department, the full requested amount must be supported. For example, a department that requested 1,000 won must be given exactly 1,000 won, and it cannot be given less than 1,000 won.

Given an array d containing the amount requested by each department and a budget, complete the solution function so that it returns the maximum number of departments that can be supported.

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

Input/Output Example #1

Each department requested [1 won, 3 won, 2 won, 5 won, 4 won]. If items are purchased for the departments that requested 1 won, 2 won, and 4 won, then 7 won out of the 9 won budget is spent, leaving 2 won. Since the exact requested amount must always be given, the remaining 2 won cannot be used to support another department. Other ways to support 3 departments are as follows.

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

Since it's not possible to purchase items for more than 3 departments, at most 3 departments can be supported.

Input/Output Example #2

Purchasing items for every department costs 10 won. So up to 4 departments can be supported.

With a bit of thought, this isn't too difficult. The goal is to allocate the budget to as many departments as possible, and for each department the budget must either be given fully or not at all. In other words, you can't give half or a partial amount.

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

Since the budget is limited, giving to the departments that requested the smallest amounts first increases the chance of supporting more departments.

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

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

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 per department
	 * @param budget: [int] budget
	 *
	 * @return [int] the 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;
	}
}