Allocation Problem in C++ – Google Kickstart

Filed Under: C++
Allocation Problem Google Kickstart

In this article, we will learn to solve the Allocation Problem: Google Kickstart 2020. It is such a popular problem because it’s already been asked in Google Kickstart. We will take a look at the problem statement and then move towards the concept lying behind the solution. And later, conclude the article by writing a program to demonstrate the algorithm.

Problem Statement

There are N houses for sale. The ith house costs Ai units of currency to buy. You have a budget of B units of currency to spend. You have to find the maximum number of houses that you can buy.

Constraints

  • 1 <= testcases <= 100
  • 0 <= budget <= 105
  • 1 <= Ai <= 1000 for all i

Concept of the Allocation Maximization Problem

Allocation is a maximization problem with a limited budget. We approach these types of problems using a greedy or dynamic programming approach. This particular problem is analogous to the fractional knapsack problem. We have a limited budget(bag) to spend, and a list of houses(items) to buy from.

We often pair greedy strategies with sorting. First, we make some greedy choices. And then, we sort the choices either in ascending or descending order. In this case, we will follow the following set of rules to write the algorithm.

Idea: To solve this problem, we will select the house that has lower-cost first.

  • Initialize a counter variable with the value zero.
  • Sort the list of price of houses in the ascending order
  • Now start iterating over this sorted list
  • At the start of each iteration, check if the budget is greater than zero
    • If the budget is less than 1, simply break out of the loop
    • Otherwise, we will proceed with the following steps.
  • First check if the price of the current item, i.e. Ai is less than the current value of the budget.
    • If Ai is less than budget, simply break out of the loop.
    • Else, we will buy this house and update the value of the budget as
      • budget -= Ai
      • And we will also increment the counter variable
  • In the end, we will return the counter variable.

That’s it, yes you are correct. The allocation problem boils down to just this many lines of code. Below is the C++ code of this algorithm.

int allocation(vector <int> prices, int budget)
{
	// initialize the counter variable
	int count = 0;

	// sort the list in the ascending order
	// the inbuilt sort function sorts in 
	// the ascending order by default
	sort(prices.begin(), prices.end());

	// now start iterating over the prices
	for(int i = 0; i < prices.size(); i++)
	{
		// initial check
		if(budget < 1)
			break;

		// otherwise
		if(prices[i] <= budget)
		{
			// buy this house
			// update budget
			// and increment
			// the counter
			budget -= prices[i];
			count++;
		}
		else
		{
			break;
		}
	}

	return count;
}

Below are a few examples to demonstrate the working of this algorithm

Example 1:
Prices: 20 90 40 90
Budget: 100
Sorted Prices: 20 40 90 90

First iteration:
Since the budget is greater than 20, we will buy this house
Count = 1
Budget = 80

Second iteration:
Again, the budget is greater than 40, we will buy this house
Count = 2
Budget = 40

Third iteration:
Now the budget is less than the current price, i.e. 90
So we break out of the loop and return the count
Ans = 2

Example 2:
Prices: 30 30 10 10
Budget: 50
Sorted Prices: 10 10 30 30

First iteration:
Since the budget is greater than 10, we will buy this house
Count = 1
Budget = 40

Second iteration:
Again, the budget is greater than 10, we will buy this house
Count = 2
Budget = 30

Third iteration:
We will buy this house because the budget is equal to the price of the current house
Count = 3
Budget = 0

Forth Iteration:
We'll break out of the loop because the budget is less than 1

Ans = 3
Algrithm
Algorithm

Allocation Problem: Google Kickstart Progam

Let’s now implement the allocation maximization problem in C++ to solve as part of the Google Kickstart program.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int allocation(vector <int> prices, int budget)
{
	// initialize the counter variable
	int count = 0;

	// sort the list in the ascending order
	// the inbuilt sort function sorts in 
	// the ascending order by default
	sort(prices.begin(), prices.end());

	// now start iterating over the prices
	for(int i = 0; i < prices.size(); i++)
	{
		// initial check
		if(budget < 1)
			break;

		// otherwise
		if(prices[i] <= budget)
		{
			// buy this house
			// update budget
			// and increment
			// the counter
			budget -= prices[i];
			count++;
		}
		else
		{
			break;
		}
	}

	return count;
}

int main()
{
	cout << "Enter the prices of the houses, press -1 to stop" << endl;
	vector <int> prices;

	while(true)
	{
		int price;
		cin >> price;

		if(price == -1)
			break;

		prices.push_back(price);
	}

	cout << "Enter the budget" << endl;
	int budget;
	cin >> budget;

	cout << "The maximum number of houses that can be bought are: " << allocation(prices, budget) << endl;

	return 0;
}

Output

Allocation Problem Output
Allocation Problem Output

Conclusion

Today we learned to solve the allocation problem that was asked in the Google Kickstart 2020. First, we went through the problem statement and then derived an algorithm. In the end, we coded a C++ program to test the working of the algorithm. The time complexity of this algorithm is O(Nlog2N). This is so because sorting takes O(Nlog2N) computational time and iteration takes O(N) time. That’s all for today, thanks for reading.

Further Readings

To learn more about knapsack or greedy algorithms, you can refer to the following websites.

https://www.journaldev.com/56879/fractional-knapsack-cpp

https://www.journaldev.com/56866/solving-0-n-knapsack-problem-in-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content