Analysis and Design of Algorithms
Practical Set : 7
AIM :
Implementation of Fractional Knapsack Problem and (0/1) Knapsack Problem.
Code :
1. Fractional Knapsack Problem.
In[]:
class Item:
def __init__(self, value, weight):
[Link] = value
[Link] = weight
def fractional_knapsack(capacity, items):
[Link](key=lambda x: [Link]/[Link], reverse=True)
total_value = 0.0
for item in items:
if capacity - [Link] >= 0:
capacity -= [Link]
total_value += [Link]
else:
fraction = capacity / [Link]
total_value += [Link] * fraction
break
return total_value
items = [Item(60, 10), Item(100, 20), Item(120, 30)]
capacity = 50
max_value = fractional_knapsack(capacity, items)
print(f"Maximum value in Knapsack = {max_value}")
Op[]:
Maximum value in Knapsack = 240.0
2. (0/1) Knapsack Problem.
In[]:
def knapsack_01(capacity, weights, values, n):
K = [[0 for x in range(capacity + 1)] for x in range(n + 1)]
for i in range(n + 1):
230175 Page | 1
Analysis and Design of Algorithms
for w in range(capacity + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif weights[i-1] <= w:
K[i][w] = max(values[i-1] + K[i-1][w-weights[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
for i in range(n + 1):
for w in range(capacity + 1):
print(K[i][w], end=" ")
print()
return K[n][capacity]
values = [12, 10, 20, 15]
weights = [2, 1, 3, 2]
capacity = 5
n = len(values)
max_value = knapsack_01(capacity, weights, values, n)
print(f"Maximum value in Knapsack = {max_value}")
Op[]:
000000
0 0 12 12 12 12
0 10 12 22 22 22
0 10 12 22 30 32
0 10 15 25 30 37
Maximum value in Knapsack = 37
Analysis:
1. Fractional Knapsack Problem:
Definition: Allows taking fractions of items to maximize the total value within a given weight
capacity.
Solution Approach: Solved using a greedy algorithm by selecting items based on their value-
to-weight ratio.
Application: Useful in fields like resource allocation and financial investments where partial
usage optimizes overall value.
2. (0/1) Knapsack Problem:
Definition: In the 0/1 Knapsack Problem, each item can either be included or excluded from the
knapsack (binary choice) to maximize the total value without exceeding the weight capacity.
Solution Approach: Solved using dynamic programming, which involves building a table to keep
track of maximum values for different capacities and using these values to determine the optimal
solution.
Application: Commonly used in resource allocation, budget management, and decision-making
scenarios where items cannot be divided.
230175 Page | 2