Suppose that you have a row of cells where each cell may or may not contain a co

Question

Suppose that you have a row of cells where each cell may or may not contain a coin. Each coin has a positive value associated with it, as well as a "radius of avoidance" within which you are not allowed to pick up any other coins. For example, if you pick up a coin at index 4 with a radius of avoidance of 2, you are not allowed to pick up the coins from indices 2, 3, 5, or 6. Your goal is to pick up coins such that you've picked up the maximum allowed value. Give a high-level description of how you could use dynamic programming to solve this problem.

Explanation / Answer

The Dynamic Programming to solve the above problem is as follows:

The user chooses the ith coin with value Vi and radius of avoidance as r. Then check if the max value is present by comparing within the radius of convergence.

i.e. The user can collect the ith coin with value Vi such that max(V(i-r),V(i-(r-1)),....,V(i),....,V(i+(r-1)),V(i+r)) = Vi

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.