Scribd
Upload
15 views4 pages

1 Dynamic Programming

The document contains implementations of various algorithms including dynamic programming techniques for the Primitive Calculator, Minimum Dot Product, and 0/1 Knapsack Problem. It also covers greedy algorithms such as Fractional Knapsack and Activity Selection Problem. Each section provides code examples and explanations for the algorithms' functionalities.

Uploaded by

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

1 Dynamic Programming

The document contains implementations of various algorithms including dynamic programming techniques for the Primitive Calculator, Minimum Dot Product, and 0/1 Knapsack Problem. It also covers greedy algorithms such as Fractional Knapsack and Activity Selection Problem. Each section provides code examples and explanations for the algorithms' functionalities.

Uploaded by

Siyamregn Yeshidagna
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

1 Dynamic Programming

1.1 Primitive Calculator:

def primitive_calculator(n):
operations = [0] * (n + 1)
parent = [0] * (n + 1)

for i in range(2, n + 1):


# Start with i-1 as predecessor
min_ops = operations[i - 1] + 1
pred = i - 1

# If divisible by 2
if i % 2 == 0 and operations[i // 2] + 1 < min_ops:
min_ops = operations[i // 2] + 1
pred = i // 2

# If divisible by 3
if i % 3 == 0 and operations[i // 3] + 1 < min_ops:
min_ops = operations[i // 3] + 1
pred = i // 3

operations[i] = min_ops
parent[i] = pred

# Reconstruct the path


sequence = []
while n > 0:
sequence.append(n)
n = parent[n]
sequence.reverse()

return operations[sequence[-1]], sequence

# Example usage:
if __name__ == "__main__":
n = int(input())
min_ops, seq = primitive_calculator(n)
print(min_ops)
print(" ".join(map(str, seq)))

1.2 Minimum Dot Product

def minimum_dot_product(a, b):


# Sort 'a' ascending and 'b' descending
a_sorted = sorted(a)
b_sorted = sorted(b, reverse=True)

# Calculate sum of products


result = sum(x * y for x, y in zip(a_sorted, b_sorted))
return result

1.3 0/1 Knapsack Problem

def knapsack(n, W, items):


dp = [0] * (W + 1)

for value, weight in items:


# Traverse in reverse to respect 0/1 constraint
for w in range(W, weight - 1, -1):
dp[w] = max(dp[w], dp[w - weight] + value)

return dp[W]

# Read input
if __name__ == "__main__":
n, W = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(n)]

print(knapsack(n, W, items))

2 Greedy Algorithms

2.1 Fractional Knapsack

def fractional_knapsack(n, W, items):


# Step 1: Calculate value per weight
items = sorted(items, key=lambda x: x[0] / x[1], reverse=True)

total_value = 0.0 # Max value we can take


for value, weight in items:
if W == 0:
break
if weight <= W:
# Take the whole item
total_value += value
W -= weight
else:
# Take the fraction that fits
total_value += value * (W / weight)
W = 0 # Bag is now full

return round(total_value, 4) # round to 4 decimal places

2.2 Activity Selection Problem

def activity_selection(activities):
# Sort activities by finish time
activities.sort(key=lambda x: x[1])

count = 0
last_finish_time = 0

for start, finish in activities:


if start >= last_finish_time:
count += 1
last_finish_time = finish

return count

# Input reading
n = int(input())
activities = [tuple(map(int, input().split())) for _ in range(n)]

# Output result
print(activity_selection(activities))

You might also like