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
How did Matt Pyke and Karsten Schmidt create the advertisement for Audi? Multiple choice question. Filmed the car as wind tossed
saw5 [17]

Matt Pyke and Karsten Schmidt wrote a programming code that created the video which they used for the advertisement for Audi. Thus, Option D is the correct statement.

<h3>What is a programming code?</h3>

Programming code refers back to the set of instructions, or a system of rules, written in a specific programming language (i.e., the source code).

It is likewise the term used for the source code after it's been processed with the aid of using a compiler and made ready to run on the computer (i.e., the object code).

Therefore, Matt Pyke and Karsten Schmidt wrote a programming code that created the video which they used for the advertisement for Audi. Option D is the correct statement.

Learn more about programming code:

brainly.com/question/25770844

#SPJ1

8 0
1 year ago
Create a program that has at least three classes. The class with main. A class that defines a Name (first name, middle name, and
Bond [772]

Answer:

See attached file for complete detailed code.

Explanation:

See attached file.

Download txt
3 0
3 years ago
Which framework can be used to develop cross-platform applications?
k0ka [10]

Answer:

Qt framework

Explanation:

3 0
3 years ago
The option to publish a file as a blog post is located in the____options on the File tab.
shtirl [24]
The answer is #2: Share
3 0
2 years ago
A(n) ________ is a heavily secured server located between a company's secure internal network and its firewall. bastion host tra
devlian [24]

Answer: Bastion host

Explanation: Bastion host is type of computer which resist the attacks happening on a network particularly. It mostly works between the internet and interior network. It assures that the interior computer network remains undamaged due to any type of threat. It can also be considered that bastion host behave as the gateway between internal network and firewall as well.

4 0
3 years ago
Other questions:
  • Which of the following is a correct definition of the term rectification? A. Rectification is the opposition to current flow in
    14·2 answers
  • vulnerability is a feebleness which allows an attacker to condense a system's information assurance to security,is it true or fa
    14·1 answer
  • Microsoft word's spell checker
    7·2 answers
  • Create a class named Console, and move all the methods that retrieve and validate user input to that class. These methods can re
    7·1 answer
  • What is an operating system? What are the main functions of a modern general purpose operating system?
    7·1 answer
  • graham drove 39 2/3 miles in 1 1/3 hours. What is the unit rate for miles per hour? Use a pencile and paper. Describe a situatio
    10·1 answer
  • Cómo se llaman los robots que se utilizan para la exploración espacial, en medicina, en la industria, en la agricultura, los que
    13·1 answer
  • If someone wouldn’t mind answering the first question for me
    14·1 answer
  • When adjusting the aperture, an F-stop of F32 lets in more light then a setting of F8
    10·1 answer
  • which server edition doesn't support any server roles that you would typically use with standard version
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!