def max_value_2_compute_all_until_max_capacity(weight_value_tuples,
											   max_capacity):
	"""
	Solution: Compute the max value for each capacity from 1 to max_capacity.
	This algorithm will always find the optimal max value, but is much
	slower than the less optimal solution and uses more space.
	Complexity:
		Time: O(n * k) (where n=number of items, k=max capacity)
		Space: O(k)
	"""
	# List to contain the max value for each capacity up to max_capacity
	# Ex: Index 1 will contain the max value of weight 1
	max_value_capacity = [0] * (max_capacity + 1)

	# For each weight from 1 to max_capacity, calculate the max value and
	# store it in our list
	for weight_to_compute_max_value_for in range(1, max_capacity + 1):
		for item_weight, item_value in weight_value_tuples:
			if item_weight <= weight_to_compute_max_value_for:
				diff = weight_to_compute_max_value_for - item_weight
				new_max_value = max_value_capacity[diff] + item_value
				max_value_capacity[weight_to_compute_max_value_for] = max(
					new_max_value,
					max_value_capacity[weight_to_compute_max_value_for])

	return max_value_capacity[max_capacity]