Charul has been given a task by Ishaan. He challenges him to fill a large container of capacity K liters. Charul has N vessels with him with different capacities.
The capacities of the vessels are given by an array A. The condition is that the container should be filled up to the brim but no water should be wasted in overflowing. Also, the vessels can't be filled partially.
Determine if Charul can fill up the container with the given conditions or not.
Assume that Charul has an unlimited supply of water.
 
Example 1:
Input: 
arr[ ] = {6, 3, 4, 2, 1} and K = 20
Output: 
1
Explanation:
The container can be filled in the following manner : 
Add water using the 6 litre vessel 3 times :
Container filled upto 18 litres
Add water using the 2 litre vessel 1 time : 
Container filled upto 20 litres
Example 2:
Input: 
arr[] = {2, 4, 3} and K = 15 
Output:  
1
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function vessel() that takes an array (arr), sizeOfArray (n), an integer K, and return the array return true if it is possible else return false. The driver code takes care of the printing.
Expected Time Complexity: O(N*K).
Expected Auxiliary Space: O(X). where X is the maximum element in an array.
Constraints : 
1 ≤ N ≤ 100
1 ≤ K ≤ 10^{3}
1 ≤ A[i] ≤ 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3



def vessel (arr, n, k) : 

    #Complete the function

    



Solutions:
def vessel(arr, n, k):
	store = set([k])
	for item in arr:
		temp = set()
		for num in store:
			while num - item >= 0:
				num -= item
				temp.add(num)
		if 0 in temp:
			return True
		store.update(temp)
	return False


def vessel(arr, n, k):
	dp = [[0] * n for i in range(k + 1)]
	for i in range(n):
		dp[0][i] = 1
	for i in range(1, k + 1):
		for j in range(n):
			if i >= arr[j]:
				dp[i][j] = dp[i - arr[j]][j] or dp[i][j - 1]
			else:
				dp[i][j] = dp[i][j - 1]
	return int(dp[k][n - 1])


def vessel(arr, n, su):
	dp = []
	for i in range(n + 1):
		dp.append([-1] * (su + 1))
	for i in range(su + 1):
		dp[0][i] = False
	for i in range(n + 1):
		dp[i][0] = True
	for i in range(1, n + 1):
		for j in range(1, su + 1):
			if arr[i - 1] <= j:
				dp[i][j] = dp[i][j - arr[i - 1]] or dp[i - 1][j]
			else:
				dp[i][j] = dp[i - 1][j]
	return dp[n][su]


def vessel(arr, n, k):
	a = [0] * (k + 1)
	for i in range(0, len(arr)):
		for j in range(1, k + 1):
			if j % arr[i] == 0 or (arr[i] < j and a[j - arr[i]] == 1):
				a[j] = 1
	return a[k]