1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Viktor [21]
3 years ago
8

Greedy Algorithm Design

Computers and Technology
1 answer:
Alik [6]3 years ago
8 0

Answer:

The algorithm is as follows:

1. Start

2. Get the number of items (n)

3. Get the current price of the n items (a1, a2..... an)

4. Get the possible hiked price of the n items (b1, b2..... bn)

5. Calculate the difference between the current and hiked prices for each item i.e. d_i = b_i - a_i

6. Sort the differences in descending order (i.e. from the greatest to the least)

7. Buy items in this order of difference

8. Stop

Explanation:

The algorithm is self-explanatory; however, what it does is that:

It takes a list of the current price of items (say list a)

E.g: a = [100, 150, 160]

Then take a list of the hiked price of the items (say list b)

E.g: b = [110, 180, 165]

Next, it calculates the difference (d) between corresponding prices d_i = b_i - a_i

d = [(110 - 100),(180-150),(165-160)]

d = [10,30,5]

Sort the difference from greatest to lowest (as the difference is sorted, lists a and b are also sorted)

d = [30,10,5]

a = [150, 100, 160]

b = [180, 110, 165]

If there is no hike up to item k, the couple would have saved (i = 1 to d[k-1])

Assume k = 3

The couple would have saved for 2 item

Savings = d[1] + d[2]

Savings = 30 +10

Savings = 40

The saved amount will then be added to the kth item in list a i.e. a[k](in this case k = 3) in order to buy b[k]

Using the assumed value of k

a[k] = a[3]

a[3] = 160

b[3] = 165

Add the saved amount (40) to a[3]

New\ Amount = 40 + 160

New\ Amount = 200

This new amount can then be used to buy b[3] i.e. 165, then they save the change for subsequent items

You might be interested in
An online game is played with two dice, explain why decomposition will be used in creating the algorithm for the game?
wolverine [178]
Decomposition will be used so you can break down the game into smaller and more manageable parts.
5 0
3 years ago
Read 2 more answers
Please select the word from the list that best fits the definition
Tasya [4]

Answer:

d

Explanation:

because it is

3 0
3 years ago
Read 2 more answers
What is computer?explain any five characteristic in short.​
miv72 [106K]

Answer:

computer is an electronic machine which work on the basic principle" ipo"(input process and output.

it's characteristics are

Accuracy

Computers perform calculations with 100% accuracy. Errors may occur due to data inconsistency or inaccuracy.

Diligence

A computer can perform millions of tasks or calculations with the same consistency and accuracy. It doesn’t feel any fatigue or lack of concentration. Its memory also makes it superior to that of human beings.

Versatility

Versatility refers to the capability of a computer to perform different kinds of works with same accuracy and efficiency.

Reliability

A computer is reliable as it gives consistent result for similar set of data i.e., if we give same set of input any number of times, we will get the same result.

4 0
2 years ago
Read 2 more answers
How to study program ?
CaHeK987 [17]
I don’t understand how this question can u explains more or be a little more specific please.
6 0
3 years ago
Design a software system for a bookstore that keeps an inventory of two types of books: Traditional books and books on CD. Books
Sophie [7]

Answer:

Explanation:

a. In this scenario, the best solution would have an Object of Traditional Books, CD, Music, Bookstore and Customer.

b. All five objects would be able to be called by the main program loop and the Customer Object would call upon and use either the Books or CD object, While the Bookstore object would call upon all of the other objects.

c. Both the Bookstore object and Customer object will "have" other objects as the Bookstore needs to hold information on every Book or CD in the Inventory. While the Customer object would call upon the Book and CD object that they are purchasing.

d. The Music Object will extend the CD object and use information on the CD object as its parent class.

e. Since the Music Object extends the CD object it is also considered a CD since it is in CD format like the Books on CD and therefore is both objects.

8 0
3 years ago
Other questions:
  • Which of the following jobs are most likely to be in greater demand due to the increasing prevalence of mobile computing? deskto
    13·1 answer
  • An IT technician has manually configured an IP address on a laptop for a new employee. Each time the employee tries to connect t
    10·1 answer
  • Julie is trying to decide weather or not to add a color scheme to her presentation and she asks you for your advice u should adv
    9·1 answer
  • User Interface Design ensures that the interface has elements that are easy to ________________. (Choose all that apply)
    10·2 answers
  • 2 Write<br>a program to and area of<br>4<br>walls. A = 2h (l+b)​
    6·1 answer
  • Which of the following shows the correct order of inventions that helped the first computers make calculations?
    9·1 answer
  • Write any two rules for writing algorithm​
    10·1 answer
  • Which of the following expressions in Java is equal to 4?
    11·1 answer
  • What ribbon command on the home tab can you use to change a cell fill color automatically
    13·2 answers
  • Organizations can face criminal or civil penalties for being ______ in protecting their sensitive data.
    6·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!