Description
-
Design a dynamic programming algorithm for the “coin row problem” but change the constraint to be: You may not pick up a new coin until you have passed up at least two coins rather than one coin as in the problem discussed by the TA’s. Thus you goal is pick up the maximum amount of money picking up coins leaving at least two coins between each picked up coin.
Example 1 2 10 5 2 3 11 1 1 1 1 12 — the answer would be to pick up coins 3(10), 7(11), 12(13) for a total of
a. Write the recurrence relation that will solve this version of the coin row problem. Recall the recurrence relation for the original coin row problem was: F(n) = max{cn + F(n-2), F(n-1)} for n > 1 F(0)=0 and F(1)=c1 Where cn is the value of the coin in the n-th position
-
-
Fill in the table to solve the above example using your recurrence relation.
-
-
Find the longest path from S to E in the graph below using a dynamic programming similar to the one used to find the shortest path in a DAG
3.
-
Design a dynamic programming algorithm for the following problem. Find the maximum total sale price, MTSP, that can be obtained by cutting a rod of n units long into integer-length pieces if the sale price of a piece i units long is pi for i = 1, 2, …, n .
|
Examples |
||||||||||
|
• Rod Length 4, p1 |
= 2 , p2 |
= 4 , p3 |
= 7 |
, p4 |
= 8 |
then MTSP = 9 sell lengths (1, 3) |
||||
|
• Rod Length 4, p1 |
= 3 , p2 |
= 7 , p3 |
= 9 |
, p4 |
= 12 |
then MTSP = 14 sell lengths (2, 2) |
||||
|
• |
Rod Length 4, p1 |
= 2 , p2 |
= 4 , p3 |
= |
7 |
, p4 |
= |
11 |
then MTSP = |
11 sell lengths (4) |
|
• |
Rod Length 4, p1 |
= 3 , p2 |
= 5 , p3 |
= |
8 |
, p4 |
= |
11 |
then MTSP = |
12 sell lengths (1, 1, 1, 1) |
The following is a rough guide to the thought process (not to be submitted) you should follow:
-
Write an English description of what you are trying to optimize along with what the parameter represents: e.g. MTSP (k)
-
Write a recurrence relation for the objective function: MTSP (k) = some function involving smaller versions of the problem. Specify the base case. This specifies the optimal substructure of the problem.
-
Determine the table you will use to keep track of the MTSP(k)? The parameter(s) in the recurrence relation most likely will determine the dimensions.
-
Fill in the table and trace back for a simple version of the problem.
Week 6 Lab Dynamic Programming.docx 1
-
Write pseudo code snippets to fill in the table and then to trace back using the table to find the rod sizes that give you the optimal solution.
-
Implement your solution in java.
Submit your program to PolyLearn: A Java class RodCutter.java. Your program should read from a text
file: “rodOptTest.txt”. The text file will contain a set of problems for your program to solve, see below. The output must be as shown!
Note: The output shows the contents of the table that is used in your dynamic programming solution to the given problem, then shows an optimal set of rod lengths.
As always, be sure to test you program before submission
INPUT FILE will not contain comments such as those shown below !!
|
2 |
// 2 test cases |
|||||||||||||||||
|
10 |
// first case rod |
of length 10 |
||||||||||||||||
|
2 4 4 |
5121314 |
15 40 41 |
// p1 = 2, p2=4 etc |
|||||||||||||||
|
16 |
// second case rod of |
length 16 |
||||||||||||||||
|
1 |
4 |
6 |
25 |
28 |
31 |
80 |
81 |
82 |
83 |
84 |
85 |
86 |
88 |
90 |
92 |
|||
|
Output: |
||||||||||||||||||
|
Case 1: |
||||||||||||||||||
|
Case 1: |
Case2: |
|||||||||||||||||
|
total |
for |
length |
1 |
= 2 |
total |
for |
length 1 |
= 1 |
||||||||||
|
total |
for |
length |
2 |
= 4 |
total |
for |
length 2 |
= 4 |
||||||||||
|
total |
for |
length |
3 |
= 6 |
total |
for |
length 3 |
= 6 |
||||||||||
|
total |
for |
length |
4 |
= 8 |
total |
for |
length 4 |
= 25 |
||||||||||
|
total |
for |
length |
5 |
= 12 |
total |
for |
length 5 |
= 28 |
||||||||||
|
total |
for |
length |
6 |
= 14 |
total |
for |
length 6 |
= 31 |
||||||||||
|
total |
for |
length |
7 |
= 16 |
total |
for |
length 7 |
= 80 |
||||||||||
|
total |
for |
length |
8 |
= 18 |
total |
for |
length 8 |
= 81 |
||||||||||
|
total |
for |
length |
9 |
= 40 |
total |
for |
length 9 |
= 84 |
||||||||||
|
total |
for |
length |
10 |
= 42 |
total |
for |
length 10 |
= 86 |
||||||||||
|
Optimal rod cutting |
total |
for |
length 11 |
= 105 |
||||||||||||||
|
Number of |
rods of length 1 |
= 1 |
total |
for |
length 12 |
= 108 |
||||||||||||
|
Number of |
rods of length 9 |
= 1 |
total |
for |
length 13 |
= 111 |
||||||||||||
|
total |
for |
length 14 |
= 160 |
|||||||||||||||
|
total |
for |
length 15 |
= 161 |
|||||||||||||||
|
total |
for |
length 16 |
= 164 |
|||||||||||||||
|
Number of |
rods of length 2 |
= 1 |
||||||||||||||||
|
Number of |
rods of length 7 |
= 2 |
||||||||||||||||
Week 6 Lab Dynamic Programming.docx 2
