Scribd
Upload
83 views3 pages

Knapsack Problem: Types and Solutions

The Knapsack Problem is a well-known optimization problem aimed at maximizing the total value in a knapsack with limited weight capacity. There are two main types: the 0/1 Knapsack, which uses dynamic programming and does not allow item splitting, and the Fractional Knapsack, which employs a greedy algorithm and allows for item fractions. Each type has its own complexity and optimal strategies for solving the problem.

Uploaded by

anshujena007
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
83 views3 pages

Knapsack Problem: Types and Solutions

The Knapsack Problem is a well-known optimization problem aimed at maximizing the total value in a knapsack with limited weight capacity. There are two main types: the 0/1 Knapsack, which uses dynamic programming and does not allow item splitting, and the Fractional Knapsack, which employs a greedy algorithm and allows for item fractions. Each type has its own complexity and optimal strategies for solving the problem.

Uploaded by

anshujena007
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

Knapsack Problem

✅ What is the Knapsack Problem?


The Knapsack Problem is a famous Greedy or Dynamic Programming problem where we try
to maximize total value we can put in a bag (knapsack) of limited weight capacity.

🔹 Types of Knapsack:
Type Item Splitting Allowed? Technique Used

0/1 Knapsack ❌ No Dynamic Programming

Fractional Knapsack ✅ Yes Greedy Algorithm

💡 1. 0/1 Knapsack (Dynamic Programming)


You either take the whole item or leave it. No fractions allowed.

🧮 Formula:
Let dp[i][w] = max value using first i items and knapsack capacity w.

# 0/1 Knapsack Problem using Dynamic Programming

def knapsack_01(weights, values, capacity):


n = len(values)
# Create a 2D dp array with size (n+1) x (capacity+1)
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

# Build the table dp[][] in bottom-up manner


for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i-1] <= w:
# Either include the item or exclude it
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
else:
# Cannot include the item
dp[i][w] = dp[i-1][w]
return dp[n][capacity]

# Example
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50

print("Maximum value (0/1 Knapsack):", knapsack_01(weights, values, capacity))

🧾 Output:
Maximum value (0/1 Knapsack): 220

💡 2. Fractional Knapsack (Greedy Algorithm)


Here you can take fractions of items to maximize value.

🧠 Strategy:
●​ Calculate value per weight.
●​ Sort items by value/weight descending.
●​ Pick the full item if it fits, else take the fraction.

# Fractional Knapsack using Greedy Approach

class Item:
def __init__(self, value, weight):
[Link] = value
[Link] = weight

def fractional_knapsack(items, capacity):


# Sort items by value-to-weight ratio in descending order
[Link](key=lambda x: [Link] / [Link], reverse=True)

total_value = 0.0

for item in items:


if capacity >= [Link]:
# Take the whole item
capacity -= [Link]
total_value += [Link]
else:
# Take the fraction of the item
total_value += [Link] * (capacity / [Link])
break # Knapsack is full

return total_value

# Example
items = [Item(60, 10), Item(100, 20), Item(120, 30)]
capacity = 50

print("Maximum value (Fractional Knapsack):", fractional_knapsack(items, capacity))

🧾 Output:
Maximum value (Fractional Knapsack): 240.0

✅ Summary:
Feature 0/1 Knapsack Fractional Knapsack

Splitting Allowed ❌ No ✅ Yes


Method Used Dynamic Programming Greedy

Complexity O(nW) O(n log n)

Optimal Strategy Consider all combos Sort by

You might also like