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
Assume the existence of a Bank Account class. Define a subclass, Savings Account that contains the following: a double instance
Finger [1]

The solution is in the attachment

5 0
3 years ago
A personal career profile for can be used to match what you know about yourself to what you know about different careers
mel-nik [20]

Answer:

B

Explanation:

give answers next time pls so i can help you!!

3 0
3 years ago
Read 2 more answers
Intro to cs 3.7 edhesive g=float(input("Enter your English test grade:")) if(g&lt;=64): print("F") if (g&gt;=65 and g&lt;69): pr
qwelly [4]

Answer:

The correct code for this question:

g=float(input("Enter your English test grade:")) #take input from user.

#check conditions

if (g>=100 and g<=90):

print ("A")

#g greater then equal to 100 and less then equal to 90.

if (g>=89 and g<=80):

print("B")

#g greater then equal to 89 and less then equal to 80.

if (g>=79 and g<=70):

print("C")

#g greater then equal to 79 and less then equal to 70.

if (g>=69 and g<=65):

print("D")

#g greater then equal to 69 and less then equal to 69.

if(g<=64):

print("F")

#g less then equal to 64.

else:

print ("Not a grade")

#not a grade or fail.

Explanation:

In this program, we use to take a value from the user and check the value from the various conditions. To check all the condition we use if-else statement and AND operator that check to the range to together.

If -else is a conditional operator. In that, If block is used to check the true part and else part takes false value, and AND is a logical operator that check the two range together  

5 0
3 years ago
What is the purpose of memory address?​
IceJOKER [234]

Answer:

A memory address is a unique identifier used by a device or CPU for data tracking.

5 0
2 years ago
Read 2 more answers
To do a good job of searching periodicals at your library, you should use A) the Library of Congress Authorities webpage. B) web
jonny [76]

Answer:

C) the online catalog.

Explanation:

An online library catalog describes the periodicals, videotapes, and books as it is the electronic bibliographic database. This evolved from the printed source, the library card catalog. Hence, this clarifies that its C. the correct option.

However, LexisNexis is the unit that gives computer-assisted research CALR and business research as well as risk management services. So through this, you can get the legal and journalistic documents.

And the stack or the book stack which is referred to as the library building block is for book storage. And the library of Congress Subject Headings is active since 1898 and holds the catalog materials which are being collected by the Library of Congress, and they do not keep track of periodicals. And the BizMiner is for financial reports.

Hence, the correct answer is the C) the online catalog.

5 0
3 years ago
Other questions:
  • When you first open office calc, the most recently saved spreadsheet opens up. A) true B) false
    14·1 answer
  • Websites that are designed to adapt gracefully to any screen size use a technique called
    5·1 answer
  • What is an accessory?
    6·1 answer
  • Read at least three (3) academically reviewed articles on Management Information Systems and complete the following activities:
    5·1 answer
  • Give an O(log m + log n)-time algorithm that takes two sorted lists of sizes m and n, respectively, as input and returns the ith
    7·1 answer
  • The Coins class was created to hold all your loose change, kind of like a piggy bank! For this exercise, you are going to simula
    15·1 answer
  • The sample remote access policy document from the hospital that you reviewed in the lab showed that the Remote Access Domain is
    15·2 answers
  • What is the function of a breadcrumb trail in a website ?
    10·2 answers
  • Write a program that uses a structure to store the following data about a customer account: Name Address City, State, and ZIP Te
    10·1 answer
  • How do you do 1.17.5, invert colors, on codehs?
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!