Scribd
Upload
7 views1 page

Knapsack Problem Pseudocode Example

The document presents a Python implementation of the knapsack problem using dynamic programming. It defines a function that calculates the maximum value that can be carried in a knapsack given weights, values, and capacity. An example usage is provided with specific weights, values, and capacity to demonstrate the function's output.

Uploaded by

rharsh995520
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
7 views1 page

Knapsack Problem Pseudocode Example

The document presents a Python implementation of the knapsack problem using dynamic programming. It defines a function that calculates the maximum value that can be carried in a knapsack given weights, values, and capacity. An example usage is provided with specific weights, values, and capacity to demonstrate the function's output.

Uploaded by

rharsh995520
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

Knapsack problem

def knapsack(weights, values, capacity):


n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]

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


for w in range(capacity + 1):
if weights[i - 1] <= w:
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
else:
dp[i][w] = dp[i - 1][w]

return dp[n][capacity]

# Example usage
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7

print("Maximum value in knapsack:", knapsack(weights, values, capacity))

You might also like