Computers and Technology, 02.09.2020 05:01 Manglethemango9450

A thief is planning on burglarizing some subset of n consecutive houses in a neighborhood. The houses are labeled 1,2,...,n and the thief will address then sequentially. The thief has an estimate of the profit to be earned from burglarizing each house pi, i = 1...n, where pi > 0. To avoid de- tection, he decides that he will never burglarize two adjacent houses, meaning that if he burglarize house 2, he cannot burglarize house 1 or house 3. Design a dynamic programming algorithm to determine the maximum total profit he can achieve. Example: In each of the following two neighborhoods, the maximum achievable profit is $100: Case 1: p= ($20, $100, $30). Case 2: p= ($40, $30, $10, $60). Your input is the list P1, P2, ...,Pnl. Your output should be the maximum profit the thief can get. You don't have to return the list of houses the thief has to burglarize to achieve the maximum. (a) Define the entries of your table in words. E. g., T(i) or T(1,j) is (b) State recurrence for entries of table in terms of smaller subproblems. (c) Write pseudocode for your algorithm to solve this problem. (d) Analyze the running time of your algorithm.

Answers: 3

Show answers

Another question on Computers and Technology

Computers and Technology, 22.06.2019 22:20

Pp 4.1 design and implement a class called sphere that contains instance data that represents the sphere’s diameter. define the sphere constructor to accept and initialize the diameter and include getter and setter methods for the diameter. include methods that calculate and return the volume and surface area of the sphere (see pp 3.5 for the formulas). include a tostring method that returns a one-line description of the sphere. create a driver class called multisphere, whose main method instantiates and updates several sphere objects.

Answers: 1

Answer

Computers and Technology, 22.06.2019 23:20

How can you tell if someone sent you a text message to your email instead of a email

Answers: 1

Answer

Computers and Technology, 23.06.2019 11:30

The most accurate readings that you can take on an analog vom are when the meter's pointer is at the a. center scale. b. extreme right. c. near right. d. extreme left.

Answers: 1

Answer

Computers and Technology, 23.06.2019 15:20

An ou structure in your domain has one ou per department, and all the computer and user accounts are in their respective ous. you have configured several gpos defining computer and user policies and linked the gpos to the domain. a group of managers in the marketing department need different policies that differ from those of the rest of the marketing department users and computers, but you don't want to change the top-level ou structure. which of the following gpo processing features are you most likely to use? a, block inheritance b, gpo enforcement c, wmi filtering d, loopback processing

Answers: 3

Answer

You know the right answer?

A thief is planning on burglarizing some subset of n consecutive houses in a neighborhood. The house...

Questions