Dynamic Programming

0-1 Knapsack

• weight → List

• value → List

• budget → int

• Each item can be chosen only once or not

• Total weight of the items chosen should be less than the budget

def Knapsack01(weight, value, budget):
	dp = [0] * (budget + 1)
	for i in range(len(weight)):
		# loop from end to beginnig to ensure each item only being added at most once
		for j in range(budget, value[i]-1, -1): 
			dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
		
	return dp[-1]

Complete Knapsack

• weight → List

• value → List

• budget → int

• Each item can be chosen for any times or zero time.

• Total weight of the items chosen should be less than the budget

def Knapsack_com(weight, value, budget):
	dp = [0] * (budget + 1)
	for i in range(len(weight)):
		# loop from beginning to end because each item can be added any times
		for j in range(value[i], budget+1): 
			dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

	return dp[-1]