[JAVA] [Algorithm] Budget

Problem description

Company A investigated how much it would take to buy things for each department in order to support the things that each department needed. However, since the overall budget is fixed, we cannot provide goods to all departments. That's why I'm trying to make it possible to buy things in as many departments as possible.

When buying things, each department must apply and support the entire amount. For example, a department that applies for 1,000 yen should always support 1,000 yen, and cannot support less than 1,000 yen.

If the array d and budget containing the amount applied for each department are given as parameters, create a solution method so that the maximum number of departments that can support things is returned.

conditions

--d is an array containing the amount applied for each department, and the length (total number of departments) is 1 or more and 100 or less. --Example) If d.length = 2, the number of departments is 2. --Example) If d [0] = 3, the application amount for department 1 is 3. --The value of d is the amount applied for each department. The application amount is a natural number of 1 or more and 100,000 or less. --Budget is a budget. The budget is a natural number of 1 or more and 10,000,000 or less.

Input / output example

d budget result
[1,3,2,5,4] 9 3
[2,2,3,3] 10 4

Commentary


import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        
        Arrays.sort(d); //Ascending sort
        
        int cnt = 0; //For counters in departments that can support
        for (; cnt < d.length; cnt++) {
            budget -= d[cnt]; //Every time we support, we will reduce from the budget
            
            if (budget < 0) break;
        }
        
        return cnt;
    }
}

Recommended Posts

[Algorithm] Budget
Java Algorithm Library-Artery-Sample