Greedy Algorithms

Being greedy for Water

You are given container full of water. Container can have limited amount of water. You also have N bottles to fill. You need to find the maximum numbers of bottles you can fill.

Input: First line contains one integer, T, number of test cases. First line of each test case contains two integer, N and X, number of bottles and capacity of the container. Second line of each test case contains N space separated integers, capacities of bottles.

Output: For each test case print the maximum number of bottles you can fill.

C++

#include <bits/stdc++.h>

using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        int numberOfBottles, capacityOfTheContainer;
        cin >> numberOfBottles >> capacityOfTheContainer;
        int A[numberOfBottles];
        for (int i = 0; i < numberOfBottles; i++) {
            cin >> A[i];
        }
        sort(A, A + numberOfBottles);
        int capacity = 0, noOfBottlesFilled = 0;
        for (int i = 0; i < numberOfBottles; i++) {
            capacity = capacity + A[i];
            if (capacity <= capacityOfTheContainer)
                noOfBottlesFilled++;
            else
                break;
        }
        cout << noOfBottlesFilled << endl;
    }
}