Master Data Science and Artificial Intelligence Semester : S1

Course: Advanced Operation Research Prof. LAYEB

Exercice 1 : Longest Common Subsequence (LCS) Problem Solution

The Longest Common Subsequence (LCS) problem is a classic dynamic programming

problem that finds the longest subsequence common to two sequences. A subsequence is a
sequence derived from another sequence by deleting some or no elements without
changing the order of the remaining elements.

Given two sequences, X of length m and Y of length n, find the length of their longest
common subsequence and the actual subsequence itself.

Dynamic Programming Approach

1. Define a DP Table: Let dp[i][j] represent the length of the LCS of the first i characters of X
and the first j characters of Y.

2. Recurrence Relation:
- If X[i-1] == Y[j-1], then dp[i][j] = dp[i-1][j-1] + 1.
- Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

3. Initialization: Initialize dp[0][j] = 0 for all j and dp[i][0] = 0 for all i because a sequence
compared with an empty sequence has an LCS of length 0.

4. Trace Back for LCS String: Starting from dp[m][n], trace back to construct the LCS by
checking the direction from which each cell’s value was derived.

Example

Apply the dynamic programming on the following example

For X = 'ABCBDAB' and Y = 'BDCAB', the output will be:

Code Implementation
def lcs(X, Y):
m, n = len(X), len(Y)

# Initialize the DP table

dp = [[0] * (n + 1) for _ in range(m + 1)]

# Fill the DP table

for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

# Length of LCS
lcs_length = dp[m][n]

# Reconstruct LCS
lcs_string = []
i, j = m, n
while i > 0 and j > 0:
if X[i - 1] == Y[j - 1]:
lcs_string.append(X[i - 1])

1
Master Data Science and Artificial Intelligence Semester : S1
Course: Advanced Operation Research Prof. LAYEB

i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1

# The LCS is constructed backwards, so reverse it

lcs_string.reverse()

return lcs_length, ''.join(lcs_string)

# Example usage
X = "ABCBDAB"
Y = "BDCAB"
length, lcs_seq = lcs(X, Y)
print("Length of LCS:", length)
print("LCS:", lcs_seq)

Example

For X = 'ABCBDAB' and Y = 'BDCAB', the output will be:

Length of LCS: 4
LCS: BCAB

Exercice 2 : Knapsack Problem

Given a list of items, each with a weight ( 𝑤𝑤 ) and value ( 𝑣𝑣 ), and a maximum capacity ( 𝑊𝑊 )
of a knapsack, find the maximum value that can fit into the knapsack.
**Solution:**
1. Define DP Table: Let dp[i][j] represent the maximum value achievable with the first i items
and capacity j.
2. Recurrence Relation:
- If the i-th item’s weight w[i-1] ≤ j, then dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1]).
- Otherwise, dp[i][j] = dp[i-1][j].
3. Initialization: Initialize dp[0][j] = 0 for all j since no items mean 0 value.

Implementation code

def knapsack(weights, values, W):

n = len(values)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(W + 1):
if weights[i-1] <= j:
dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1])
else:
dp[i][j] = dp[i-1][j]
return dp[n][W]

2
Master Data Science and Artificial Intelligence Semester : S1
Course: Advanced Operation Research Prof. LAYEB

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
W=7
print("Maximum Value:", knapsack(weights, values, W)) # Output: 9

Step-by-Step Calculation

Table Initialization

Create a table dp with dimensions (n+1) x (W+1), initialized to zero.

Table Filling Steps

1. Item 1 (weight 1, value 1):

o For w = 1 to w = 7, include the item:
 dp[1][w] = max(dp[0][w], dp[0][w-1] + 1)
2. Item 2 (weight 3, value 4):
o For w = 3 to w = 7, consider inclusion:
 dp[2][w] = max(dp[1][w], dp[1][w-3] + 4)
3. Item 3 (weight 4, value 5):
o For w = 4 to w = 7, consider inclusion:
 dp[3][w] = max(dp[2][w], dp[2][w-4] + 5)
4. Item 4 (weight 5, value 7):
o For w = 5 to w = 7, consider inclusion:
 dp[4][w] = max(dp[3][w], dp[3][w-5] + 7)

Final DP Table

i\w 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 1 1 1 1 1 1
2 0 1 1 4 5 5 5 5
3 0 1 1 4 5 6 6 9
4 0 1 1 4 5 7 8 9

Explanation

• Decisions: At each step, decide whether to include an item based on maximizing

value without exceeding capacity.
• Result: The maximum value is 9, found at dp[4][7].

Exercise 3: Edit Distance Problem

Given two strings, find the minimum number of operations required to convert one string
into the other using insertions, deletions, and substitutions.

3
Master Data Science and Artificial Intelligence Semester : S1
Course: Advanced Operation Research Prof. LAYEB

Solution:
1. Define DP Table: Let dp[i][j] represent the minimum edit distance between the first i
characters of string A and the first j characters of string B.
2. Recurrence Relation:
- If A[i-1] == B[j-1], dp[i][j] = dp[i-1][j-1].
- Otherwise, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
3. Initialization: Initialize dp[i][0] = i and dp[0][j] = j for all i, j.
4. Example:

def edit_distance(A, B):

m, n = len(A), len(B)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]

A = "sunday"
B = "saturday"
print("Edit Distance:", edit_distance(A, B)) # Output: 3

Exercise 4. Coin Change Problem

Given an array of coin denominations and a total amount, find the minimum number of
coins needed to make that amount. If it cannot be made, return -1.

Solution:
1. Define DP Array: Let dp[i] represent the minimum number of coins needed to make
amount i.
2. Recurrence Relation: For each coin c, dp[i] = min(dp[i], dp[i - c] + 1) if i >= c.
3. Initialization: Initialize dp[0] = 0 since no coins are needed to make amount 0, and dp[i] =
infinity for i > 0 initially.

4. Example: apply on the example: amount to return 270$, with available coins
100$,50$,20$,10$,5$,1$

Here’s the step-by-step execution for the coin change problem on an amount of $270, with
available coins of $100, $50, $20, $10, $5, and $1:

4
Master Data Science and Artificial Intelligence Semester : S1
Course: Advanced Operation Research Prof. LAYEB

We'll initialize a dynamic programming table (dp) where dp[i] holds the minimum number of
coins needed to make the amount i. We'll also include an additional list to track the coin
choices at each step.

Initialization:

• dp[0] = 0 (no coins are needed to make an amount of $0).

• Set dp[i] to infinity for all other i from $1 to $270 initially.

Execution Table (only a sample is shown due to the length, but this continues up to i = 270):

Amount (i) dp[i] Before Coin Options dp[i] After Chosen Coins for dp[i]

1 ∞ 1 1 1

2 ∞ 1 2 1, 1

... ... ... ... ...

5 ∞ 5, 1 1 5

10 ∞ 10, 5, 1 1 10

20 ∞ 20, 10, 5, 1 1 20

50 ∞ 50, 20, 10, 5, 1 1 50

100 ∞ 100, 50, 20, 10, 5, 1 1 100

105 ∞ 100, 50, 20, 10, 5, 1 2 100, 5

... ... ... ... ...

270 ∞ 100, 50, 20, 10, 5, 1 4 100, 100, 50, 20

By the end, dp[270] = 4 using coins [100, 100, 50, 20].

The implementation in python

def min_coins(coins, amount):

dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if i >= coin:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1

coins = [1, 2, 5]
amount = 11
print("Minimum Coins Needed:", min_coins(coins, amount)) # Output: 3

5
Master Data Science and Artificial Intelligence Semester : S1
Course: Advanced Operation Research Prof. LAYEB

Problem.

The Build-tablet Company has agreed to supply its best customer with three Tablets during
each of the next 3 weeks, even though producing them will require some overtime work.
The relevant production data are as follows:

Maximum Production, Maximum Production, Production Cost per Unit

Week Regular Time Overtime Regular Time

1 2 2 $300

2 3 2 $500

3 1 2 $400

The cost per unit produced with overtime for each week is $100 more than for regular time.
The cost of storage is $50 per unit for each week it is stored. There is already an inventory of
two Tablets on hand currently, but the company does not want to retain any Tablets in
inventory after the 3 weeks.

Management wants to know how many units should be produced in each week to
minimize the total cost of meeting the delivery schedule.

Let us solve this by using dynamic programming.

Application of Dynamic Programming

The decisions that need to be made are the number of units to produce each week,
so the decision variables are

xn = number of Tablets to produce in week n, for n = 1, 2, 3.

To choose the value of xn, it is necessary to know the number of Tablets already on hand at
the beginning of week n. Therefore, the “state of the system” then is

sn = number of Tablets on hand at the beginning of week n, for n = 1, 2, 3.

Because of the shipment of three Tablets to the customer each week, note that

sn+1 = sn + xn -3.

Also note that two Tablets are on hand at the beginning of week 1, so

s1 = 2.

To introduce symbols for the data given in the above table for each week n, let

6
Master Data Science and Artificial Intelligence Semester : S1
Course: Advanced Operation Research Prof. LAYEB

cn = unit production cost in regular time,

rn = maximum regular time production,

mn = maximum total production.

The corresponding data are given in the following table.

n rn mn cn

1 2 4 300

2 3 5 500

3 1 3 400

We wish to minimize the total cost of meeting the delivery schedule, so our measure
of performance is total cost. For n = 1, 2, 3, let

pn(sn, xn) = cost incurred in week n when the state is sn and the decision is xn.

Thus,

p n ( s n , x n ) = c n x n + 100 max(0, x n − rn ) + 50 max(0, s n + x n − 3) .

Using the notation in Sec. 10.2, let

𝑓𝑓𝑛𝑛∗ (𝑠𝑠𝑛𝑛 )= optimal cost for week n onward (through the end of week 3) when starting
week n in state sn, for n = 1, 2, 3.

Given sn, the feasible values of xn are the integers such that xn ≤ mn and xn ≥ 3 - sn (assuming
sn ≤ 3) in order to provide the customer with 3 Tablets in week n. Thus, because
sn+1 = sn + xn - 3, the optimal value of xn (denoted by xn*) is obtained from the following
recursive relationship.

∗
𝑓𝑓𝑛𝑛∗ (𝑠𝑠𝑛𝑛 ) = 𝑚𝑚𝑚𝑚𝑚𝑚 [𝑝𝑝𝑛𝑛 (𝑠𝑠𝑛𝑛 , 𝑥𝑥𝑛𝑛 ) + 𝑓𝑓𝑛𝑛+1 (𝑠𝑠𝑛𝑛 + 𝑥𝑥𝑛𝑛 − 3)],
3−𝑠𝑠𝑛𝑛 ≤𝑥𝑥𝑛𝑛 ≤𝑚𝑚𝑛𝑛

where

𝑓𝑓4∗ (𝑠𝑠4 ) = 0 for s4 = 0.

7
Master Data Science and Artificial Intelligence Semester : S1
Course: Advanced Operation Research Prof. LAYEB

Recall that the company does not want to retain any Tablets in inventory after the
three weeks, so s4 = 0. Therefore, the optimal policy for week 3 obviously is to produce just
enough Tablets to have a total of three to ship to the customer, so

s4= 3 - s3.

Given 𝑓𝑓4∗ (𝑠𝑠4 ) and 𝑓𝑓3* (𝑠𝑠3 )), we can use the recursive relationship to solve for the optimal
policy for week 2 and then for week 1. These calculations are shown below.

For n = 3:

s3 f3*(s3) x3 *

0 1,400 3

1 900 2

2 400 1

3 ≤ s3 0 0

For n = 2:

x2 f2(s2, x2) = p2(s2, x2)+ f3*(s2+ x2-3) f2*(s2) x2 *

s2 0 1 2 3 4 5

0 2,900 3,050 3,200 2,900 3

1 2,400 2,450 2,600 2,850 2,400 2

2 1,900 1,950 2,000 2,250 2,900 1,900 1

3 1,400 1,450 1,500 1,650 2,300 2,950 1,400 0

For n = 1:

x1 f1(s1, x1) = p1(s1, x1)+ f2*(s1+ x1-3) f1*(s1) x1 *

s1 0 1 2 3 4

2 3,200 3,050 3,000 2,950 2,950 4

Hence, the optimal plan is to produce four Tablets in period 1, store three of them until
period 2, and produce three in period 3, with a total cost of $2,950.