Mark and toys

Maximum toys in Go

Problem Statement

There are a number of toys lying in from of him, tagged with their prices. Mark has an only a certain amount to spend, and he wants to maximize the number of toys he buys with his money. Given a list of toy prices and a amount to spend, determine the maximum number of gift he can buys. Each toy can only be purchased once.

Considerations

1. There are a number of toys tagged with their prices. It means we have an slice [1, 4, 7, 3, 4, 9] .
2. Certain amount to spend, 7 . It means we have a target.
3. Maximize the number of toys he can buy.

Combinatorial problems?

A combinatorial problem consists in, given a finite collection of objects and a set of constraints, finding an object of the collection that satisfies all constraints

Let’s try to understand the problem and break it in steps:

1. Find all combinations(no way) in an slice that are equal or less than a target.
2. Then, choice the largest one. And return their size

Pardon me, for such naibe approach. The truth is that we don’t really care about all the combinations. And it would be a waste of time and effort. Leading to an unnecessary increase in complexity and taken us to extrange solutions.

A little more Thinking (hopefully 🤞)

What we really need is to find the largest combination that satisfy the constraint and return their size. Neat! But then how?

Let’s do some research!

Greedy algorithms

Greedy is an algorithm paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefits. So the problems where choosing locally optimal also leads to global solution are the best fit for greedy.

Characteristics of Greedy algorithm

• There must be an ordered list of resources
• Maximum of all the resources are taken

It is called greedy because it tries to find the solution by making the best choice at each stage, without considering the future steps or the consequences of the current decision.

Greedy algorithms fit the best for, Scheduling and resource allocation, Minimum spanning trees, Coin change problem, Huffman coding.

Greedy algorithms base structure

1. Sort the list
2. Declare an empty result
3. Make a greedy choice to select, if the solution is feasible then add it to the result
4. Return the result

The algorithm O(n)

1. The function maximumToys takes two arguments: a slice of toy prices prices and a budget k.
2. The function first sorts the toy prices in ascending order. This is done using the sort.Slice function, which takes the slice as the first argument and a comparison function as the second argument. The comparison function in this case is a lambda function that compares two prices and returns true if the first price is less than the second price.
3. After the toy prices are sorted, the function iterates over the slice and keeps track of the maximum number of toys that can be bought with the budget k.
4. In each iteration, the function adds the current toy price to a running sum. If the running sum exceeds the budget, then the function breaks out of the loop. Otherwise, the function increments the counter of the maximum number of toys that can be bought.
5. Finally, the function returns the maximum number of toys that can be bought.

Maximum number of toys

Why sorting? anyway

This is truly interesting (it was for me), since we are told we need to maximize the number of toys we can buy (the more toys we can buy the better). Putting the cheapest toys at first makes sense [1 2 3 4 5 6]. So instead of finding all the combinations possible, we found the largest one. And the largest one is the combination of the elements (toys) that are in the first locations of the slice. Ta Da! We did it in linear time O(n).

Resources

Mark and Toys | HackerRank

HackerRank

Combinatorial Problem Solving

Greedy Algorithms - GeeksforGeeks

Introduction to Greedy Algorithm - Data Structures and Algorithm Tutorials - GeeksforGeeks