Scribd
Upload
14 views13 pages

The Coin Row Problem - Dynamic Programming Approach

The document discusses the Coin Row optimization problem, where the goal is to select non-adjacent coins from a row to maximize their total value. It outlines the constraints, recurrence relations, base cases, and provides an algorithm for calculating the maximum amount collectible. The example illustrates the calculation process and the identification of the optimal set of coins that yield the maximum value.

Uploaded by

pallavi.bsmh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views13 pages

The Coin Row Problem - Dynamic Programming Approach

The document discusses the Coin Row optimization problem, where the goal is to select non-adjacent coins from a row to maximize their total value. It outlines the constraints, recurrence relations, base cases, and provides an algorithm for calculating the maximum amount collectible. The example illustrates the calculation process and the identification of the optimal set of coins that yield the maximum value.

Uploaded by

pallavi.bsmh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DYNAMIC PROGRAMMING SERIES

The Coin Row


Optimization Problem
A Bottom-Up Strategy for Maximum Collection
Defining the Row

Initial Configuration

We are presented with a row of n coins, each


possessing a specific integer value denoted as:

(c₁, c₂, ..., cₙ)

The core objective is to select a subset of these coins


that yields the maximum total value while strictly
adhering to proximity constraints.
The Fundamental Constraint

No Adjacency Maximum Amount Optimal Substructure

No two selected coins can be The goal is to maximize the The global optimal solution
adjacent in the initial row. If total monetary sum F(n) of can be derived from the
you pick coin i, you cannot the chosen coins. optimal solutions of smaller
pick i-1 or i+1. sub-rows.
The Recurrence Relation

To compute the maximum value for the first n coins, we choose the best of two possibilities:

Option A: Include Coin n Option B: Exclude Coin n


Take value cₙ and add the result from the row skipping the Discard cₙ and take the best result possible from the row of
neighbor (up to n-2). n-1 coins.
Defining Base Cases

Zero Coins One Coin

If there are no coins in the row, the maximum If there is only one coin, the maximum amount
amount collected is obviously zero. is simply the value of that single coin.
Algorithm: CoinRow(C[1..n])

Step Instruction
Initialize

0
1
]

0
Note: This executes in O(n) time and O(n) space.

Initialize

F
Tracing a Scenario

Input Sequence

Let's consider a row of 6 coins with the following


values:

[5, 1, 2, 10, 6, 2]

• Base cases defined: F[0]=0, F[1]=5


• Iterate from index 2 to 6
Calculation: i=2 and i=3

Value C[2] = 1 Value C[3] = 2

F[2] = max(1 + F[0], F[1]) F[3] = max(2 + F[1], F[2])


= max(1 + 0, 5) = 5 = max(2 + 5, 5) = 7

Reasoning:
Reaching the End

Continuing the iterative calculation for the


remaining coins:

i = 4 (Value 10):
max(10 + F[2], F[3]) = max(10 + 5, 7) = 15

i = 5 (Value 6):
max(6 + F[3], F[4]) = max(6 + 7, 15) = 15

i = 6 (Value 2):
max(2 + F[4], F[5]) = max(2 + 15, 15) = 17
The Complete F-Table

Index (i) 0 1 2 3 4 5 6

Coin (C) - 5 1 2 10 6 2

Result (F) 0 5 5 7 15 15 17

Maximum possible amount to collect: 17


Finding the Optimal Set

To identify the specific coins, we backtrack from F[6]:

Step 3
Step 2
Step 1
Move to F[2]
Move to F[4] F[2] = 5
F[6] = 17 F[4] = 15
Used C[6] + Achievement via
Used C[4] + F[2] F[1]
F[4] C[4]=10
C[6]=2 included C[1]=5 included
included

Selected Coins: { C[1], C[4], C[6] } → Values: { 5, 10, 2 } = 17


Questions & Strategy
How does this strategy scale? Can we modify the constraint to skip 2 coins
instead of 1?

Presented by: Dynamic Programming Module


Image Sources

[Link]

Source: [Link]

[Link]

Source: [Link]

[Link]

Source: [Link]

[Link]

Source: [Link]

You might also like