Design a dynamic programming algorithm

Assignment Help Computer Engineering

Reference no: EM132139771

Question :

Suppose you are buying stamps to put on a package at the post office.

The postage required to send the package is N dollars. You can buy $1, $7, and $10 stamps. You want to find the minimum number of stamps required so that you have at least SIV worth of stamps. Note that the solution to this problem may not actually be the cheapest solution in terms of dollars: for example, if you need stamps totaling $16, then you can buy a $10 and a $7 stamp, which adds up to $17.

Or you could buy a $10 stamp and six $1 stamps, which adds up to $16. The second solution requires seven stamps, so the first solution is better (even though it is more expensive). However, if there are multiple solutions that use the same number of stamps, then you should return the one that is cheapest.

Design a dynamic programming algorithm that finds the minimum number of stamps required. The input to your algorithm is the total desired postage value N. The output should be the number of stamps required. (You do not have to tell me which stamps were used.)

Part a: Draw the DAG corresponding to this problem. Hint: Let the nodes correspond to different total postage values, and let the edges correspond to different stamp choices.

Part b: Solve the dynamic programming problem using your DAG. Hint: Once you have drawn the DAG correctly, the original problem becomes a very simple graph problem on the DAG.

Reference no: EM132139771

Questions Cloud

Find a key by exhaustive search if the keyspace is of size : What is the expected time (in years) to find a key by exhaustive search if the keyspace is of size 288?

Confidence interval for the mean claim payment : How would I calculate this: Anystate Auto Insurance Company took a random sample of 382 insurance claims paid out during a 1-year period.

Analyze financial statements of a publicly traded company : Assignment - Write a financial analysis for a U.S.-based, publicly traded organization. Analyze the financial statements of a publicly traded company

Find a point estimate for p : Let p represent the proportion of Santa Fe black-on-white potsherds at the excavation site. Find a point estimate for p. (Round your answer to four decimal plac

Design a dynamic programming algorithm : Design a dynamic programming algorithm that finds the minimum number of stamps required. The input to your algorithm is the total desired postage value N.

Would you choose the default system parameters : Would you choose the default system parameters when installing the system software? Explain and support your answer with reasoning.

What is the running time of your algorithm : Design a recursive algorithm that constructs T from S1 and S2. Note that it is enough for your algorithm to describe the children of each node.

How many blocks pf main memory are there : What is the format of a memory address as seen by the cache, that is what are the sizes of the tag, block and offset fields.

Paper - state of the economy effects on assets management : Write a paper of 8-10 pages, double-spaced that discusses the following in detail: The state of the economy's effects on assets' management

User Account

All Pages