Example: Solve 0/1 Knapsack Problem in Python

C
C++
C#
Java
Python
PHP
# Solve 0/1 Knapsack Problem in Python
import sys

# This will return max size of the value
def maxSize(a, b):
	pass
	return a if a > b else b

# This function will solve the 0 1 knapsack problem
def solveKnapSack(W, wt, val, n):
	pass

	if n == 0 or W == 0:
		return 0
	# 1. If the weight of the nth item is more than
	# 2. Knapsack capacity W, then this item cannot be included in the optimal solution
	if wt[n - 1] > W:
		return solveKnapSack(W, wt, val, n - 1)

	# It returns the maximum of two cases:
	# 1. nth item included
	# 2. not included
	else:
		return maxSize(val[n - 1] + solveKnapSack(W - wt[n - 1], wt, val, n - 1), solveKnapSack(W, wt, val, n - 1))

# It's the driver code
val, wt, W = [60, 100, 120], [10, 20, 30], 50

n = int (sys.getsizeof(val) / sys.getsizeof(val[0]))

# This will print the solution of 0-1 Knapsack problem
print ("The solution of 0-1 Knapsack problem is: ", solveKnapSack(W, wt, val, n))