In this blog we will list the advance data structure questions which is related to "greedy algorithms". By solving these questions you can get good knowledge in data structure programming. If you face any issue then our expert provide the full support to solving these questions with affordable price.
Example 1: Money Change
Problem Introduction
In this problem, you will design and implement an elementary greedy algorithm used by cashiers all over the world millions of times per day.
Problem Description
Task.
The goal in this problem is to find the minimum number of coins needed to change the input value (an integer) into coins with denominations 1, 5, and 10.
Input Format.
The input consists of a single integer 𝑚. Constraints. 1 ≤ 𝑚 ≤ 103 .
Output Format.
Output the minimum number of coins with denominations 1, 5, 10 that changes 𝑚.
Sample 1.
Input: 2
Output: 2
2 = 1 + 1.
Sample 2.
Input: 28
Output: 6
28 = 10 + 10 + 5 + 1 + 1 + 1.
Example 2: Maximum Value of the Loot
Problem Introduction
A thief finds much more loot than his bag can fit. Help him to find the most valuable combination of items assuming that any fraction of a loot item can be put into his bag.
Problem Description
Task.
The goal of this code problem is to implement an algorithm for the fractional knapsack problem.
Input Format.
The first line of the input contains the number 𝑛 of items and the capacity 𝑊 of a knapsack. The next 𝑛 lines define the values and weights of the items. The 𝑖-th line contains integers 𝑣𝑖 and 𝑤𝑖—the value and the weight of 𝑖-th item, respectively.
Constraints. 1 ≤ 𝑛 ≤ 103 , 0 ≤ 𝑊 ≤ 2 · 106 ; 0 ≤ 𝑣𝑖 ≤ 2 · 106 , 0 < 𝑤𝑖 ≤ 2 · 106 for all 1 ≤ 𝑖 ≤ 𝑛. All the numbers are integers.
Output Format.
Output the maximal value of fractions of items that fit into the knapsack. The absolute value of the difference between the answer of your program and the optimal value should be at most 10−3 . To ensure this, output your answer with at least four digits after the decimal point (otherwise your answer, while being computed correctly, can turn out to be wrong because of rounding issues).
Sample 1.
Input:
3 50
60 20
100 50
120 30
Output:
180.0000
To achieve the value 180, we take the first item and the third item into the bag.
Sample 2.
Input:
1 10
500 30
Output:
166.6667
Here, we just take one third of the only available item.
Example 3: Car Fueling
Problem Introduction
You are going to travel to another city that is located 𝑑 miles away from your home city. Your car can travel at most 𝑚 miles on a full tank and you start with a full tank. Along your way, there are gas stations at distances stop1 ,stop2 , . . . ,stop𝑛 from your home city. What is the minimum number of refills needed?
Problem Description
Input Format.
The first line contains an integer 𝑑. The second line contains an integer 𝑚. The third line specifies an integer 𝑛. Finally, the last line contains integers stop1 ,stop2 , . . . ,stop𝑛.
Output Format.
Assuming that the distance between the cities is 𝑑 miles, a car can travel at most 𝑚 miles on a full tank, and there are gas stations at distances stop1 ,stop2 , . . . ,stop𝑛 along the way, output the minimum number of refills needed. Assume that the car starts with a full tank. If it is not possible to reach the destination, output −1.
Constraints. 1 ≤ 𝑑 ≤ 105 . 1 ≤ 𝑚 ≤ 400. 1 ≤ 𝑛 ≤ 300. 0 < stop1 < stop2 < · · · < stop𝑛 < 𝑑.
Sample 1.
Input:
950
400
4
200 375 550 750
Output: 2 The distance between the cities is 950, the car can travel at most 400 miles on a full tank. It suffices to make two refills: at points 375 and 750. This is the minimum number of refills as with a single refill one would only be able to travel at most 800 miles.
Sample 2.
Input:
10
3
4
1 2 5 9
Output:
-1
One cannot reach the gas station at point 9 as the previous gas station is too far away.
Sample 3.
Input:
200
250
2
100
150
Output:
0
There is no need to refill the tank as the car starts with a full tank and can travel for 250 miles whereas the distance to the destination point is 200 miles.
Example 4: Maximum Advertisement Revenue
Problem Introduction
You have 𝑛 ads to place on a popular Internet page. For each ad, you know how much is the advertiser willing to pay for one click on this ad. You have set up 𝑛 slots on your page and estimated the expected number of clicks per day for each slot. Now, your goal is to distribute the ads among the slots to maximize the total revenue.
Problem Description
Task.
Given two sequences 𝑎1, 𝑎2, . . . , 𝑎𝑛 (𝑎𝑖 is the profit per click of the 𝑖-th ad) and 𝑏1, 𝑏2, . . . , 𝑏𝑛 (𝑏𝑖 is the average number of clicks per day of the 𝑖-th slot), we need to partition them into 𝑛 pairs (𝑎𝑖 , 𝑏𝑗 ) such that the sum of their products is maximized.
Input Format.
The first line contains an integer 𝑛, the second one contains a sequence of integers 𝑎1, 𝑎2, . . . , 𝑎𝑛, the third one contains a sequence of integers 𝑏1, 𝑏2, . . . , 𝑏𝑛. Constraints. 1 ≤ 𝑛 ≤ 103 ; −105 ≤ 𝑎𝑖 , 𝑏𝑖 ≤ 105 for all 1 ≤ 𝑖 ≤ 𝑛.
Output Format.
Output the maximum value of ∑︀𝑛 𝑖=1 𝑎𝑖𝑐𝑖 , where 𝑐1, 𝑐2, . . . , 𝑐𝑛 is a permutation of 𝑏1, 𝑏2, . . . , 𝑏𝑛.
Sample 1.
Input: 1
23
39
Output:
897
897 = 23 · 39.
Sample 2.
Input: 3
1 3 -5
-2 4 1
Output:
23
23 = 3 · 4 + 1 · 1 + (−5) · (−2).
Example 5: Collecting Signatures
Problem Introduction
You are responsible for collecting signatures from all tenants of a certain building. For each tenant, you know a period of time when he or she is at home. You would like to collect all signatures by visiting the building as few times as possible.
The mathematical model for this problem is the following. You are given a set of segments on a line and your goal is to mark as few points on a line as possible so that each segment contains at least one marked point.
Problem Description
Task.
Given a set of 𝑛 segments {[𝑎0, 𝑏0], [𝑎1, 𝑏1], . . . , [𝑎𝑛−1, 𝑏𝑛−1]} with integer coordinates on a line, find the minimum number 𝑚 of points such that each segment contains at least one point. That is, find a set of integers 𝑋 of the minimum size such that for any segment [𝑎𝑖 , 𝑏𝑖 ] there is a point 𝑥 ∈ 𝑋 such that 𝑎𝑖 ≤ 𝑥 ≤ 𝑏𝑖 .
Input Format.
The first line of the input contains the number 𝑛 of segments. Each of the following 𝑛 lines contains two integers 𝑎𝑖 and 𝑏𝑖 (separated by a space) defining the coordinates of endpoints of the 𝑖-th segment.
Constraints. 1 ≤ 𝑛 ≤ 100; 0 ≤ 𝑎𝑖 ≤ 𝑏𝑖 ≤ 109 for all 0 ≤ 𝑖 < 𝑛.
Output Format.
Output the minimum number 𝑚 of points on the first line and the integer coordinates of 𝑚 points (separated by spaces) on the second line. You can output the points in any order. If there are many such sets of points, you can output any set. (It is not difficult to see that there always exist a set of points of the minimum size such that all the coordinates of the points are integers.)
Sample 1.
Input:
3
1 3
2 5
3 6
Output:
1
3
In this sample, we have three segments: [1, 3], [2, 5], [3, 6] (of length 2, 3, 3 respectively). All of them contain the point with coordinate 3: 1 ≤ 3 ≤ 3, 2 ≤ 3 ≤ 5, 3 ≤ 3 ≤ 6.
Example 6: Maximum Number of Prizes
Problem Introduction
You are organizing a funny competition for children. As a prize fund you have 𝑛 candies. You would like to use these candies for top 𝑘 places in a competition with a natural restriction that a higher place gets a larger number of candies. To make as many children happy as possible, you are going to find the largest value of 𝑘 for which it is possible.
Problem Description
Task.
The goal of this problem is to represent a given positive integer 𝑛 as a sum of as many pairwise distinct positive integers as possible. That is, to find the maximum 𝑘 such that 𝑛 can be written as 𝑎1 + 𝑎2 + · · · + 𝑎𝑘 where 𝑎1, . . . , 𝑎𝑘 are positive integers and 𝑎𝑖 ̸= 𝑎𝑗 for all 1 ≤ 𝑖 < 𝑗 ≤ 𝑘.
Input Format. The input consists of a single integer 𝑛.
Constraints. 1 ≤ 𝑛 ≤ 109 .
Output Format. In the first line, output the maximum number 𝑘 such that 𝑛 can be represented as a sum of 𝑘 pairwise distinct positive integers. In the second line, output 𝑘 pairwise distinct positive integers that sum up to 𝑛 (if there are many such representations, output any of them).
Sample 1.
Input:
6
Output:
3
1 2 3
Sample 2.
Input:
8
Output:
3
1 2 5
Sample 3.
Input:
2
Output:
1
2
Example 7: Maximum Salary
Problem Introduction
As the last question of a successful interview, your boss gives you a few pieces of paper with numbers on it and asks you to compose a largest number from these numbers. The resulting number is going to be your salary, so you are very much interested in maximizing this number. How can you do this?
In the lectures, we considered the following algorithm for composing the largest number out of the given single-digit numbers.
Unfortunately, this algorithm works only in case the input consists of single-digit numbers. For example, for an input consisting of two integers 23 and 3 (23 is not a single-digit number!) it returns 233, while the largest number is in fact 323. In other words, using the largest number from the input as the first number is not a safe move.
Your goal in this problem is to tweak the above algorithm so that it works not only for single-digit numbers, but for arbitrary positive integers.
Problem Description
Task. Compose the largest number out of a set of integers.
Input Format. The first line of the input contains an integer 𝑛. The second line contains integers 𝑎1, 𝑎2, . . . , 𝑎𝑛.
Constraints. 1 ≤ 𝑛 ≤ 100; 1 ≤ 𝑎𝑖 ≤ 103 for all 1 ≤ 𝑖 ≤ 𝑛.
Output Format. Output the largest number that can be composed out of 𝑎1, 𝑎2, . . . , 𝑎𝑛.
Sample 1.
Input:
2
21 2
Output: 221
Note that in this case the above algorithm also returns an incorrect answer 212.
Sample 2.
Input: 5
9 4 6 1 9
Output: 99641
In this case, the input consists of single-digit numbers only, so the algorithm above computes the right answer.
Sample 3.
Input: 3
23 39 92
Output: 923923
As a coincidence, for this input the above algorithm produces the right result, though the input does not have any single-digit numbers.
What To Do Interestingly, for solving this problem, all you need to do is to replace the check digit ≥ maxDigit with a call IsGreaterOrEqual(digit, maxDigit) for an appropriately implemented function IsGreaterOrEqual. For example, IsGreaterOrEqual(2, 21) should return True.
If you have any query related to these problems then comment in below comment section and share your own solution.
If you need any help related to Data Structure then also contact us or send your requirement details at:
realcode4you@gmail.com