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
Using the simple alphabet code below, you will decode and encode the message. Write the Full
gladu [14]

Answer:

acefghijlmb2d4k1113589136510waynopqrtuvx2261415161718202122232425

Explanation:

6 0
3 years ago
Will mark Brainliest, need help ASAP!
Whitepunk [10]

Answer:

What Sherman needs to configure is:

RIPv2 class D of 240.

Explanation:

Multicast messages are usually dispatched to a select group of hosts on a network and require acknowledgement of the recipients. RIPv2 is a router-based internet protocol for exchanging routing information to the IP address 224.0. 0.9 on a network. It determine the most efficient way to route data on a network and to prevent routing loops.

3 0
2 years ago
Given that Jamie worked 50 hours (Hours = 50) last week and earns $10.00 an hour (Rate = 10), how much did Jamie earn last week,
quester [9]

Answer:

<em>Jamie earned (Total pay)  $500.</em>

<em></em>

Explanation:

We are given the following code:

<em>If (Rate >=10) OR (Hours <=40) Then </em>

<em>    TotalPay = Hours * Rate </em>

<em>Else </em>

<em>    TotalPay = (Hours * Rate)+(Hours–40)*Rate*1.5 </em>

<em>End If</em>

<em />

Let us understand the code line by line:

The first line contains an if statement with 2 conditions:

i.e. 1st condition:

The rate is greater than or equal to 10

2nd condition:

Number of hours are lesser than or equal to 40.

There is OR between the two condition i.e. the statement next to if() statement will get executed if any one of them becomes true and else part will not be executed.

The next statement is:

TotalPay = Hours * Rate

It calculates the pay if any of the two conditions written earlier becomes true.

Next statement is else statement:

It will get executed given that the above if() statement becomes false.

Now, we are given that Jamie worked 50 hours last week and earns $10.00 an hour:

i.e.

Hours = 50

Rate = 10

Now, let get to the code execution.

The first condition is true i.e. Rate >= 10 (because Rate is 10 here)

So, the following statement will be used to calculate the Total pay:

TotalPay = Hours * Rate

and else part will not be executed.

TotalPay = 50 * 10  =<em> $500  </em>

<em></em>

<em>Jamie earned (Total pay)  $500.</em>

3 0
3 years ago
Linux is: Select one: a. primarily concerned with the tasks of end users. b. designed for specific machines and specific micropr
ivann1987 [24]

Answer:

C. an example of open-source software.

Explanation:

open-source software is the type of software in which anyone can access, it can also be shared And modified by anyone simply because ita accessible to the public.

Hence and open source software's source code can be

inspected, enhanced and modified by anyone. A typical example is Linux.

7 0
3 years ago
You can run a macro by:
oee [108]

Selecting the button assigned

Using the shortcut Keys assigned

Explanation:

By clicking the assigned button one can run a macro and we can assign a short cut key to macro which we created.

So, the two options we can use to run a macro.

7 0
3 years ago
Other questions:
  • If you wanted to search for emails containing the word advanced and prevent emails containing the word new from appearing in the
    14·1 answer
  • What country threatens Denmark at the beginning of Hamlet as evidenced in Marcellus’s question, "Why this same strict and most o
    13·1 answer
  • Turning up the transmit power or utilizing a high gain antenna to reach wireless users from a distance increases your exposure t
    12·1 answer
  • This is the thing that I don't understand why did they banned private chat like there are long-distance relationships, and frien
    13·2 answers
  • All systems have ___________.
    9·2 answers
  • State and give reason, if the following variables are valid/invalid:
    12·1 answer
  • ```{r}
    11·1 answer
  • If a TextView has not been displayed yet, it is possible to retrieve measurements about its width and height using the _________
    7·1 answer
  • What is Frederick Taylor attributed to doing
    15·1 answer
  • In _________, the process requests permission to access and modify variables shared with others. a) entry section b) critical se
    14·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!