Greedy Algorithms

A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem.

Question 01

Sandun is a wine lover. He had to be in his home for three months due to the Covid-19 situation. Sandun wants to buy some wine since the curfew has been lifted. He goes to his favorite wine yard with some empty bottles. The wine yard owner is pleased to see Sandun. Hence, he offers Sandun free wine on one condition. Sandun can fill only the bottles he carries in his bag.

Wine barrels in the wine yard have a tag in each one of them which has two values containing the number of bottles in the barrel and the price of the whole barrel.

You have to build a program to help Sandun to take maximum valued wine from this offer. Given the number of bottles that he brought and the information on the wine barrels, you have to find the maximum value of wines Sandun gets from this deal.

Please note that he cannot fill any of the bottles with more than one type of wine. Assume that the bottle is a 750ml glass bottle.

Input Format

First Line contains two integers N and M. N is the number of bottles Sandun brought and M is the number of barrels in the wine yard.

Second-line contains M space-separated integers contain the volume of barrels in bottles.

The third line contains the M space-separated integers containing the price of each barrel.

Output Format

One integer containing the maximum value of wines Sandun gets from the offer.

Sample Input

5 3

1 2 3

6 10 12

Sample Output

24

Explanation

He can fill one bottle from 1st barrel, two bottles from 2nd barrel, and another 2 bottles from the third barrel which gives a maximum value of 24.

Question 02

Manel is a school teacher. She wants to give some face masks to the students in her class. All the students sit in a line and each of them has a score according to his or her performance in the class. Students can’t change their seating order. Manel wants to give at least 1 face mask to each student. If two students sit next to each other, then the one with the higher score must get more face masks. Note that when two children have equal scores, they are allowed to have different numbers of face masks. Manel wants to minimize the total number of face masks she must buy.

For example, assume her students' scores are [4, 6, 4, 5, 6, 2]. She gives the students face mask in the following minimal amounts: [1, 2, 1, 2, 3, 1]. She must buy a minimum of 10 face masks.

You have to develop a program to help her find the minimum number of face masks she should buy.

Input Format

The first line contains an integer, n, the number of students to give face masks.

Each of the next n lines contains an integer score[i] indicating the score of the student at position i.

Constraints

1 ≤ n ≤ 105

1 ≤ score[i] ≤ 105

Output Format

Output a single line containing the minimum number of face masks Manel must buy.

Sample Input

3

1

2

2

Sample Output

4

Explanation

Here 1, 2, 2 is the score. Note that when two children have equal scores, they are allowed to have different numbers of face masks. Hence optimal distribution will be 1, 2, 1.

Question 03

Seetha works for an online store that uses airmail to send ordered products. But due to the covid-19 situation, they have to ship the products using containers. Her task is to then determine the lowest cost way to combine her orders for shipping. She has a list of product weights. The shipping company has a requirement that all products loaded in a container must weigh less than or equal to 4 units plus the weight of the minimum weight product. Otherwise, they will not take responsibility for addresses getting defaced. All products meeting that requirement will be shipped in one container.

You have to develop a program to find the minimum number of containers required.

For example, there are products with weights w=[1,2,3,4,5,10,11,12,13]. This can be broken into two containers: [1,2,3,4,5] and [10,11,12,13]. Each container will contain products weighing within 4 units of the minimum weight product.

Input Format

The first row includes an integer n, the number of shipping products.

The next line includes the weight sequence of products in n space-separated integers.

Constraints

1 ≤ n ≤ 105

0 ≤ weight ≤ 104

Output Format

Return a single integer containing the minimum number of containers needed.

Sample Input

8

1 2 3 21 7 12 14 21

Sample Output

4

Explanation

We need 4 containers.

1st one can hold 1,2 and 3.

2nd one to hold 7.

3rd one can hold 12 and 14.

Finally, 4th one can hold both products weighing 21.

Answers for these 3 questions are in my Github repository.

https://github.com/HarshanaWalpita/Greedy-Algorithms


Comments

Post a Comment

Popular posts from this blog

Programming Using GNU Octave

Image
  Questions: 1 A small object is projected from a toy gun to travel some distance and land on the ground. 1. Write a function to model the dynamics of the object in Octave called f_trajectory. f_trajectory will accept following arguments in the same order (measured in the given units). Also specify the default values for each parameter as given in brackets. i. h(5) : Initial height of the projectile (m) ii. g(9.81) : acceleration from gravity (m/s/s) iii. v(25) : speed at initial release (m/s) iv. theta(π/4) : angle of release (radians) v. t : a vector representing the points in time For default values of t check if the variable ‘exist’ with name ‘t’ and type ‘var’ if not initialize it as a row vector starting from 0 and goes to 5 with increments of 0.1. If x is distance and y is height, the equations below describe their dependence on time and all the other parameters. 𝑥(𝑡)=𝑣𝑐𝑜𝑠(𝜃)𝑡 ----------------(eq1) 𝑦(𝑡)=ℎ+𝑣𝑠𝑖𝑛(𝜃)𝑡− 12𝑔𝑡2 ---------------(eq2) Convert the above e
Read more

Library Problem

Image
A giant library has just been inaugurated this week. It can be modeled as a sequence of N consecutive shelves with each shelf having some number of books. No, think of the following two queries which can be performed on these shelves. ● Change the number of books in one of the shelves. ● Obtain the number of books on the shelf having the kth rank within the range of shelves. A shelf is said to have the kth rank if its position is k when the shelves are sorted based on the number of the books they contain, in ascending order. Can you write a program to simulate the above queries? Input Format : The first line contains a single integer T, denoting the number of test cases. The first line of each test case contains an integer N denoting the number of shelves in the library. The next line contains N space separated integers where the ith integer represents the number of books on the ith shelf where 1<=i<=N. The next line contains an integer Q denoting the number of queries to
Read more

What Is A Gamma Ray Burst?

Image
Imagine if you could gather the energy from every star within a hundred million light-years. From thousands of galaxies, each with billions of stars. Imagine, you could take this kind of power, and use it to fire the biggest super-weapon in the universe. Imagine the damage you could do. It turns out, you don't need to imagine it. These exist, and they're called gamma-ray bursts. But what are these cosmic snipers? And what happens if one takes a shot at Earth? To understand gamma-ray bursts, we first have to understand gamma rays. Gamma rays are electromagnetic radiation – waves that carry energy just like visible light. Visible light is a tiny part of the electromagnetic spectrum: it's the part your eyes can see. At lower energies, there are radio waves, microwaves, and infrared. And at higher energies: ultraviolet, x-rays, and gamma rays. Gamma rays are incredibly powerful. A single gamma-ray photon is more energetic than a million visible photons combined. Their
Read more