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
makkiz [27]
3 years ago
12

Barr the Bear has started a business to sell fish to Poe and his fellow penguins. The penguin customers submit many fish orders,

but Barr can only process one order at a time. Suppose that Barr currently has orders from n penguin customers (label them as 1, 2, . . . , n). Customer i’s order takes ti time to complete. Barr is going to process each penguin’s order one by one, and the scheduling of orders can be described as a permutation of the customers. Let Ci denote the completion time of order i. For instance, if customer j’s order is the first to be completed, then we would have Cj = tj (assume Barr begins processing orders at time 0); if customer k’s order is the second to be completed after that, then Ck = Cj + tk = tj + tk, and so on. Each customer is of different importance to Barr’s business, and we denote this relative weight by wi (for customer i). Barr wishes to minimize the weighted sum of the completion times of n orders, Pn i=1 wi · Ci . Intuitively, the more important a customer is, the sooner Barr wishes to complete the customer’s order. Design an O(n log n) algorithm to solve this problem to help Barr. You are given a set of n orders with a processing time ti and a weight wi for each customer i (assume ti , wi are positive integers). You want to decide an ordering of the customer orders so as to minimize the weighted sum of the completion times. Prove correctness of your algorithm (i.e., optimality) and analyze its runtime.
Computers and Technology
1 answer:
luda_lava [24]3 years ago
5 0

Answer:

Algorithm below designed using Java

Explanation:

import java.util.SortedMap;

import java.util.TreeMap;

import java.util.Vector;

public class SchedulingProblem {

static Vector<Integer> processTime = new Vector<>();

static Vector<Integer> processWeight = new Vector<>();

static SortedMap<Integer, Double> timeWeightRatio = new TreeMap<Integer, Double>() {

};

 

static int number = 2;

public static void main(String[] args) {

processTime.add(1);

processWeight.add(10);

processTime.add(3);

processWeight.add(2);

for (int i = 0; i < number; i++) { // O(N)

timeWeightRatio.put(i, processWeight.get(i) / (processTime.get(i) * 1.0)); // O(log(n))

}

// ------------ O(nlog(n))

int sum = 0, tmpTime = 0;

while (timeWeightRatio.size() > 0) { // O(n)

tmpTime += processTime.get(timeWeightRatio.firstKey()); // O(n)

sum += processWeight.get(timeWeightRatio.firstKey()) * tmpTime; // O(n)

System.out.print(processWeight.get(timeWeightRatio.firstKey()) + " * " + tmpTime + ((timeWeightRatio.size() > 1) ? " + " : " = " + sum));

timeWeightRatio.remove(timeWeightRatio.firstKey()); // O(log(n))

}

 

// >>>> O(nlog(n))

}

}

You might be interested in
.WAP to enter monthly sale of Salesman and give him commission i.E. If the monthly sale is more than 500000 then commision will
nexus9112 [7]

sales = float(input("Enter monthly sales amount: $"))

commission = 0.05

if sales> 500000:

   commission = 0.1

print("You earned: $"+str(sales*commission))

I wrote my code in python 3.8. I hope this helps.

5 0
3 years ago
The ____ is the period of time within which systems, applications, or functions must be recovered after an outage. Select one:
scZoUnD [109]

Answer:

c. recovery time objective                                                  

Explanation:

  • Recovery time objective (RTO) is the maximum acceptable duration permitted between an unfortunate loss or failure and the restoration of normal operations and services.
  • According to the RTO, the systems, applications or operations must be restored within a targeted time period after a disaster, to avoid unacceptable outcomes of the disruption.
  • So a business process must be recovered within this period of time.
  • It measures how much a failure affects the normal operations, applications and systems and RTO is measures in time units like seconds minutes hours or days.
  • In simple words RTO refers to the time you need to restore system, applications and data.
  • For instance a 2-hour RTO refers to restore and get operations or services back to running within 2 hours of the service failure or outrage.
6 0
3 years ago
A menu within a menu is called what?​
Aneli [31]

Answer:

a submenu

Explanation:

a menu inside a menu is called a submenu or recursive menu

4 0
3 years ago
Computers and technology<br> Help 10 Points!!!!
jonny [76]
Hi!

The answers are:
For the bookmark one, it is A. Below address bar
For the edge printing one, it is again A. Options
For the last one, it is C. Internet Explorer

-ASIAX ·<span>Frequent Answerer</span>
3 0
3 years ago
How is an orthographic drawing similar or different from an isometric drawing
Savatey [412]
An Isometric drawing<span> is a quasi 3d </span>drawing<span> that shows the height width and depth of the object in a single view where the viewpoint is at a 45 degree angle from each of the perpendicular planes of the </span>orthographic<span> view. </span>Isometric<span> differs from a perspective view in that all lengths are shown true length.</span>
6 0
3 years ago
Other questions:
  • What three steps Name a group??
    14·1 answer
  • How does a layered pattern make use of abstraction and encapsulation?
    10·1 answer
  • The _____ handles the instructions for your computer to start up before the operating system is loaded.
    10·1 answer
  • Why is plastic durable?
    9·2 answers
  • 2.13) A simple rule to estimate your ideal body weight is to allow 110 pounds for the first 5 feet of height and 5 pounds for ea
    15·1 answer
  • It keeps saying “something is going wrong oops!” when i click on my brainly notifications what do I do
    9·1 answer
  • During data declaration, a name is binded to a memory location, what else can be identify as part of this process?
    12·1 answer
  • If you want to transfer information transform STM to LTM, it is essential that you make the information ______________________.
    9·1 answer
  • Many phone fraud scammers are expessily cunning because they approach the target to try to sell
    9·1 answer
  • Can anyone help me out with my photography questions?
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!