Reference no: EM132092900
A person is shopping at a store that carries n different food items as packaged goods. A box of the i-th item will bring the shopper a benefit of bi and costs pi dollars, where bi and pi are integers.
The shopper would like to receive maximum benefit, subject to the requirement that they can't spend more than P dollars in total. So, the problem is which boxes to take (they can take multiple boxes of the same item).
This is known as the integral shopping problem. In the fractional shopping problem, the same n items are sold in bulk, so the shopper can take as much or as little as they like of each food item, instead of having to buy a whole box or nothing.
1. Suppose that the items have the same order if we sort them by price from low to high, and if we sort them by benefit from high to low. Give an efficient algorithm to find an optimal solution to the integral shopping problem in this special case, and argue that your algorithm is correct. Hint: Describe the algorithm in English (1 line). Argue correctness in 3 lines.
2. Prove that the fractional version has the following property: the optimal solution can be found by making a series of locally optimal choices. Therefore, give a greedy algorithm to solve this version and proof it correct. Hint: Ditto.
Solve using Dynamic Programming:
1) Write the identity for the OPT value.
2) Explain why the identity holds.
3) Describe data structure you will use to store OPT value for the subproblems and the order in which you will fill out the entries in your data structure.
4) In the problems you are asked to return the solution ( not just the value of the solution), state the additional information you record which will allow you to retrace your steps and report an optimal solution.
5) Bound the running time by the size of the data structure and the work per entry in it.
Create a coin toss simulation program
: A no-arg constructor, which randomly determines the side of the coin, that is facing up ("heads" or "tails") and initializes the sideUp field accordingly.
|
How frequently should the key be changed
: What attack is more likely to succeed if a key has been used frequently? How frequently should the key be changed?
|
Update the credit hours and classification
: Update the credit hours, classification, and the GPA, taking into account the current GPA and grades in the courses the student is currently enrolled in.
|
Insert at least five sample rows of data into the employee
: The database should have a table named Employee , with columns for employee ID, name, position, and hourly pay rate.
|
Describe data structure you will use to store opt value
: Describe data structure you will use to store OPT value for the subproblems and the order in which you will fill out the entries in your data structure.
|
Write an algorithm for the following input two numeric value
: If the second is larger than the first, perform a real division. Otherwise, perform an integer division.
|
How do you call a subroutine called myprogram
: Write the code to assign "Dean", "Sam", "Castiel", "Bobby", and "Charlie" to the Perl equivalent of an array.
|
Write a script that prompts the user for a date
: Use the code that reads a single character to ask the user to press a key indicating whether they want to compare to today or another date.
|
Could a shortage of paid code checkers mean there might
: Because OpebSSL is open source, could a shortage of paid code checkers mean there might be more errors like Heartbleed? Why?
|