Determine schedule that obtains maximum amount of profit

Assignment Help Data Structure & Algorithms

Reference no: EM1350206

Q1) Assume you have one machine and a set of n jobs a1, a2, ..., an to process on that machine. Each job aj has an integer processing time tj, a profit pj and an integer deadline dj. The machine can process only one job at a time, and job aj must run uninterruptedly for tj consecutive time units. If job aj is completed by its deadline dj, you receive a profit pj, but if it is completed after its deadline, you receive a profit of 0. Give a dynamic programming algorithm to find the schedule that obtains the maximum amount of profit. What is the running time of your algorithm?

Reference no: EM1350206

Questions Cloud

Compare the current and previous impact on shareholders : Currently a company has $1 million in 10 percent debt. The firm also has 50,000 shares outstanding that sell for $40 each. The company used the $1.0 million to repurchase stock.

Determine the speed vb of the spacecraft at point b : The total mechanical energy of the spacecraft, assume that the gravitational potential energy is zero at an infinite distance from the Earth.

Create class diagram for company has number of employees : Create a class diagram for following problem. A company has a number of employees. Attributes of employee include employeeID (primary key), name, address, and birthdate.

Determine the final speed of the more massive cart : A long, straight wire carries a 25.0 current. An electron is fired parallel to this wire with a speed of 280 in the same direction as the current, 2.30 from the wire.

Determine schedule that obtains maximum amount of profit : Assume you have one machine and a set of n jobs a1, a2, ..., an to process on that machine. Determine the schedule that obtains the maximum amount of profit. Compute the running time of your algorithm?

Current and future trends in financial services : Suppose if you were managing a small bank or insurance agency in your local community, what current and future trends in financial services & institutions would likely have the greatest impact on institution.

Which proposal would you favor : The regression results are presented on the next page. Based on this information, which proposal would you favor.

Determine how many proton-proton chain fusion cycles : A spaceship moves past you at speed v. You measure the ship to be 287 m long, whereas an astronaut on the ship measures a length of 380 m. Find out v.

Describe the characteristics of the persuader : Who - Describe the Characteristics of the Persuader: What influences our ability to become persuaded by someone? What specific characteristics must this person possess?

User Account

All Pages