nvshah/Pizzeria.py

## Pizzeria.py
# M - max pizza's slices
# N - number of pizza
M,N = map(int, input().split())
#Slices Count for each pizza
slicesCount = list(map(int, input().split()))
#To store memoized values for given pizza & given desired slice at moment
pizzeria = []
# List of pizza selected to fulfill the order
selectedPizza = []
#Memoization, (DP)
for i in range(N+1):
        pizzeria.append([0 if i==0 or j==0 else max(pizzeria[i-1][j], slicesCount[i-1] + pizzeria[i-1][j-slicesCount[i-1]]) if slicesCount[i-1]<=j else pizzeria[i-1][j] for j in range(M+1) ])
#BackTracking to get minimum pizz with max slices, fulfilling demand as effectively as possible
while True:
    if N==0 or M==0:
        break
    while slicesCount[N-1] > pizzeria[N][M] :
        N -= 1
        if N == 0:
            break
    while True:
        if pizzeria[N-1][pizzeria[N][M] - slicesCount[N-1]] == pizzeria[N][M] - slicesCount[N-1]:
            break
        else:
            N -= 1
            if N == 0:
                break
    selectedPizza.append(N-1)
    M = pizzeria[N][M] - slicesCount[N-1]
    N -= 1
#Output
print(len(selectedPizza),' '.join(map(str, sorted(selectedPizza))),sep='\n')

### Extra....... Explanation
# ( Smaple input ) :
# 26 6
# 1 5 8 13 20 25
# ( Smaple Ouptput ):
# 2
# 0 5
### i.e 1st pizza(1 slices) & 6th pizza(25 slices) can be one of the solution

## Pizzeria_GA_V1.py
def findPizzas(N, M):
    '''
    find whether to include pizza at given number row N in pizzeria matrix ( with given Slices count i.e sliceCount[N-1] ) for M slices in solution
    { find contributing pizza from pizza ID lying inside (1 to N) so that M slices or max count less than M can be attained if possible
    pizza Id for each pizza is rowNumber on which pizza is resting in pizzeria matrix }
    '''
    if N==0 or M==0:
        return
    # It's not going to be contributing, since its value after adding makes greater value than what we desired
    while slicesCount[N-1] > pizzeria[N][M] :
        N -= 1
        if N == 0:
            return
    # Check if this pizza can be included as contributor
    if pizzeria[N-1][pizzeria[N][M] - slicesCount[N-1]] == pizzeria[N][M] - slicesCount[N-1]:
        selectedPizza.append(N)                             # Select Current Pizza
        findPizzas(N-1,pizzeria[N][M] - slicesCount[N-1])   # Go down to find which pizza can fullfill the required/left slices figures
    else:
        if pizzeria[N][M] != maxValue:                      # Inorder to avoid unnecessary later redundant call with the same pizza, if pizza is one to be the largest contributor of slices
            findPizzas(N-1, M)                              # If pizza is not largest slices contributor then step down to find the other next major contributor down in herirachy

M,N = map(int, input().split())                             # Fetch Values : M - max slices to order, N - total number of pizza
slicesCount = list(map(int, input().split()))               # get slices for N Pizza
pizzeria = []                                               # To store memoized values for given pizza & given desired slice at moment
selectedPizza = []                                          # List of pizza selected to fulfill the order, contains the number of pizza starting from 1, 2, ...N
possibleWays = []                                           # Total Number of Possible Ways to achieve the max slices

# preparing the pizzeria matrix that give info about how much max slices can be possible with available pizza's at moment
for i in range(N+1):
        pizzeria.append([0 if i==0 or j==0 else max(pizzeria[i-1][j], slicesCount[i-1] + pizzeria[i-1][j-slicesCount[i-1]]) if slicesCount[i-1]<=j else pizzeria[i-1][j] for j in range(M+1) ])

maxValue = pizzeria[N][M]                                   # Rightmost element in last row will be our interest to find about
while True:
    if pizzeria[N][M] != maxValue:                          # Find all possible solution for M slices among N pizza's
        break
    findPizzas(N, M)                                        # find solution for Nth pizza with slicesCount[N-1] slices
    if len(selectedPizza) != 0:
        possibleWays.append(selectedPizza)
        selectedPizza = []                                  # Go for next possible solution
    N -= 1

print("Possible Solutions (stating pizza number starting from 1...N ): ")
for i in possibleWays:
    print(i, sum(map(lambda i: slicesCount[i-1], i)))       # print each solution with sum of slices at the end inorder to verify the validity

print("Possible efficacious solutions (stating pizza number starting from 1...N ): ")
minLength = len(min(possibleWays, key=len))                 # find the solutuion with minimum pizza count fulfilling slices requirement

# Efficient solution i.e minimum pizza and max slices
efficientWays = [i for i in possibleWays if len(i) == minLength]
for i in efficientWays:
    print(i, sum(map(lambda i: slicesCount[i-1], i)))       # print each solution with sum of slices at the end inorder to verify the validity

###Extra...Sample
## Input:
# 26 6
# 1 5 6 8 13 20 25
## Output:
# Possible solutions (stating pizza number starting from 1...N ) :
# [7, 1] 26
# [6, 3] 26
# [5, 4, 2] 26
# Explaination sol_1 : 7th(25 slices) & 1st(1 slice)
#              sol_2 : 3rd(6 slices) & 6th(20 slices)
#              sol_3 : 5th(13 slices), 4th(8 slices) & 2nd(5 slices)
# Possible efficacious solutions (stating pizza number starting from 1...N ):
# [7, 1] 26
# [6, 3] 26
# Explanation sol_1 & sol_3 from above as they both possess minimum pizza i.e 2 pizza only
##
###Over

## Pizzeria_GA_V2.py
import logging

### Globals-------------------------------------------------------------------------------------------------------------------
pizzeria = []                   # To store memoized values for given pizza & given desired slice at moment
selectedPizza = []              # List of pizza selected to fulfill the order, contains the number of pizza starting from 1, 2, ...N
possibleWays = []               # Total Number of Possible Ways to achieve the max slices

### Functions-------------------------------------------------------------------------------------------------------------------
def findPizzas(N, M):
    '''
    find whether to include pizza at given number row N in pizzeria matrix ( with given Slices count i.e sliceCount[N-1] ) for M slices in solution
    { find contributing pizza from pizza ID lying inside (1 to N) so that M slices or max count less than M can be attained if possible
    pizza Id for each pizza is rowNumber on which pizza is resting in pizzeria matrix }
    '''
    if N==0 or M==0:
        return

    # It's not going to be contributing, since its value after adding makes greater value than what we desired
    while slicesCount[N] > pizzeria[N][M] :
        N -= 1
        if N == 0:
            return

    leftOver = pizzeria[N][M] - slicesCount[N]         # left required slices after removing slices from current pizza (N)

    # Check if this pizza (N) can be included as contributor
    if pizzeria[N-1][leftOver] == leftOver:
        selectedPizza.append(N)                        # Select Current Pizza
        logging.info(f'Pizza number : {N}, slices : {slicesCount[N]}, demand : {M}')
        findPizzas(N-1, leftOver)   # Go down to find which pizza can fullfill the required/left slices figures
    else:
        if pizzeria[N][M] != maxValue:             # Inorder to avoid unnecessary later redundant call with the same pizza, if pizza is one to be the largest contributor of slices
            findPizzas(N-1, M)                     # If pizza is not largest slices contributor then step down to find the other next major contributor down in herirachy

### Main Code ------------------------------------------------------------------------------------------------------------

showLogs = input('\nDo you wanna display logs (for tracking) ?  { y/n } : ')

while showLogs not in ('y', 'Y', 'n', 'N'):
    showLogs = input('invalid input ! try again : ')

if showLogs in ('y', 'Y'):
    print('\n------------------------------------------------ Logs -----------------------------------------------------------------')
    logging.basicConfig(level=logging.DEBUG)
else:
    logging.disable(logging.CRITICAL)

logging.info('***Task Started*** \n')
logging.info('=> Fetching inputs ... ')

# Fetch Values : M - max slices to order, N - total number of pizza
M,N = map(int, input('\nEnter number of Slices to Order & number of pizza available (seperated by spaces): ').strip().split()[:2])
# get slices for N Pizza
slicesCount = [0, *list(map(int, input('Enter Slices for each pizza in Non-Decreasing order (seperated by pizza) ').strip().split()[:N]))]
# preparing the pizzeria matrix that give info about how much max slices can be possible with available pizza's at moment
for i in range(N+1):
        pizzeria.append([0 if i==0 or j==0 else max(pizzeria[i-1][j], slicesCount[i] + pizzeria[i-1][j-slicesCount[i]]) if slicesCount[i]<=j else pizzeria[i-1][j] for j in range(M+1)])

maxValue = pizzeria[N][M]                                   # Rightmost element in last row will be our interest to find about
while True:
    if pizzeria[N][M] != maxValue:                          # Find all possible solution for M slices among N pizza's
        break
    if slicesCount[N] <= pizzeria[N][M]:
        logging.info(f'Backtracking for pizza - {N} --------')
        findPizzas(N, M)                                        # find solution for Nth pizza with slicesCount[N] slices
        if any(selectedPizza):
            possibleWays.append(selectedPizza)
            selectedPizza = []                                  # Go for next possible solution
    N -= 1

if showLogs in ('y', 'Y'):
    print('\n---------------------------------------------- Logs Over ---------------------------------------------------------------')

print("\nPossible Solutions (stating pizza number starting from 1...N ): ")
for i in possibleWays:
    print(i, sum(map(lambda i: slicesCount[i], i)))  # print each solution with sum of slices at the end inorder to verify the validity

minLength = len(min(possibleWays, key=len))          # find the solutuion with minimum pizza count fulfilling slices requirement
efficientWays = list(filter(lambda way: len(way) == minLength, possibleWays)) # Efficient solution i.e minimum pizza and max slices

print("Possible efficacious solutions (stating pizza number starting from 1...N ): ")
for i in efficientWays:
    print(i, sum(map(lambda i: slicesCount[i], i)))  # print each solution with sum of slices at the end inorder to verify the validity

## Pizzeria_GA_V2M.py
import logging

### Globals-------------------------------------------------------------------------------------------------------------------
pizzeria = []                   # To store memoized values for given pizza & given desired slice at moment
selectedPizza = []              # List of pizza selected to fulfill the order, contains the number of pizza starting from 1, 2, ...N
possibleWays = []               # Total Number of Possible Ways to achieve the max slices


### Functions-------------------------------------------------------------------------------------------------------------------

def findPizzas(N, M):
    '''
    find whether to include pizza at given number row N in pizzeria matrix ( with given Slices count i.e sliceCount[N-1] ) for M slices in solution
    { find contributing pizza from pizza ID lying inside (1 to N) so that M slices or max count less than M can be attained if possible
    pizza Id for each pizza is rowNumber on which pizza is resting in pizzeria matrix }
    '''
    if N==0 or M==0:
        return

    # It's not going to be contributing, since its value after adding makes greater value than what we desired
    while slicesCount[N] > pizzeria[N][M] :
        N -= 1
        if N == 0:
            return

    leftOver = pizzeria[N][M] - slicesCount[N]         # left required slices after removing slices from current pizza (N)

    if leftOver:                                  # demand is not yet fulfilled / It's partially pacified
        if pizzeria[N-1][leftOver] == leftOver:         # Check if this pizza (N) can be included as contributor
            selectedPizza.append(N)                     # Select Current Pizza
            logging.info(f'Pizza number : {N}, slices : {slicesCount[N]}, demand : {M}')
            findPizzas(N-1, leftOver)   # Go down to find which pizza can fullfill the required/left slices figures
        else:
            if pizzeria[N][M] != maxValue:             # Inorder to avoid unnecessary later redundant call with the same pizza, if pizza is one to be the largest contributor of slices
                findPizzas(N-1, M)                     # If pizza is not largest slices contributor then step down to find the other next major contributor down in herirachy
    else:                                        #  demand is completely fulfilled
        selectedPizza.append(N)
        logging.info(f'Pizza number : {N}, slices : {slicesCount[N]}, demand : {M}')

### Main Code ---------------------------------------------------------------------

showLogs = input('\nDo you wanna display logs (for tracking) ?  { y/n } : ')

while showLogs not in ('y', 'Y', 'n', 'N'):
    showLogs = input('invalid input ! try again : ')

if showLogs in ('y', 'Y'):
    print('\n------------------------------------------------ Logs -----------------------------------------------------------------')
    logging.basicConfig(level=logging.DEBUG)
else:
    logging.disable(logging.CRITICAL)

logging.info('***Task Started*** \n')
logging.info('=> Fetching inputs ... ')

# Fetch Values : M - max slices to order, N - total number of pizza
M,N = map(int, input('\nEnter number of Slices to Order & number of pizza available (seperated by spaces): ').strip().split()[:2])
# get slices for N Pizza
slicesCount = [0, *list(map(int, input('Enter Slices for each pizza in Non-Decreasing order (seperated by pizza) ').strip().split()[:N]))]
# preparing the pizzeria matrix that give info about how much max slices can be possible with available pizza's at moment
for i in range(N+1):
        pizzeria.append([0 if i==0 or j==0 else max(pizzeria[i-1][j], slicesCount[i] + pizzeria[i-1][j-slicesCount[i]]) if slicesCount[i]<=j else pizzeria[i-1][j] for j in range(M+1) ])

maxValue = pizzeria[N][M]                                   # Rightmost element in last row will be our interest to find about
while True:
    if pizzeria[N][M] != maxValue:                          # Find all possible solution for M slices among N pizza's
        break
    if slicesCount[N] <= pizzeria[N][M]:
        logging.info(f'Backtracking for pizza - {N} --------')
        findPizzas(N, M)                                    # find solution for Nth pizza with slicesCount[N] slices
        if any(selectedPizza) :
            possibleWays.append(selectedPizza)
            selectedPizza = []                              # Go for next possible solution, Here create new empty list as list is mutable
    N -= 1

if showLogs in ('y', 'Y'):
    print('\n---------------------------------------------- Logs Over ---------------------------------------------------------------')

print("\nPossible Solutions (stating pizza number starting from 1...N ): ")
for i in possibleWays:
    print(i, sum(map(lambda i: slicesCount[i], i)))  # print each solution with sum of slices at the end inorder to verify the validity

minLength = len(min(possibleWays, key=len))          # find the solutuion with minimum pizza count fulfilling slices requirement
efficientWays = list(filter(lambda way: len(way) == minLength, possibleWays)) # Efficient solution i.e minimum pizza and max slices

print("\nPossible efficacious solutions (stating pizza number starting from 1...N ): ")
for i in efficientWays:
    print(i, sum(map(lambda i: slicesCount[i], i)))  # print each solution with sum of slices at the end inorder to verify the validity

###Extra...Sample
## Input:
# 26 6
# 1 5 6 8 13 20 25
## Output:
# Possible solutions (stating pizza number starting from 1...N ) :
# [7, 1] 26
# [6, 3] 26~
# [5, 4, 2] 26
# Explaination sol_1 : 7th(25 slices) & 1st(1 slice)
#              sol_2 : 3rd(6 slices) & 6th(20 slices)
#              sol_3 : 5th(13 slices), 4th(8 slices) & 2nd(5 slices)
# Possible efficacious solutions (stating pizza number starting from 1...N ):
# [7, 1] 26
# [6, 3] 26
# Explanation sol_1 & sol_3 from above as they both possess minimum pizza i.e 2 pizza only
##
###Over

## Pizzeria_O1.py
def findPizzas(N, M):
    '''
    find whether to include pizza at given number row N in pizzeria matrix ( with given Slices count i.e sliceCount[N-1] ) for M slices in solution
    { find contributing pizza from pizza ID lying inside (1 to N) so that M slices or max count less than M can be attained if possible
    pizza Id for each pizza is rowNumber on which pizza is resting in pizzeria matrix }
    '''
    if N==0 or M==0:
        return
    # It's not going to be contributing, since its value after adding makes greater value than what we desired
    while slicesCount[N-1] > pizzeria[N][M] :
        N -= 1
        if N == 0:
            return
    # if pizzeria[N][M] == maxValue:
    #     tracked.append(N)

    # Check if this pizza can be included as contributor
    if pizzeria[N-1][pizzeria[N][M] - slicesCount[N-1]] == pizzeria[N][M] - slicesCount[N-1]:
        selectedPizza.append(N)                             # Select Current Pizza
        findPizzas(N-1,pizzeria[N][M] - slicesCount[N-1])   # Go down to find which pizza can fullfill the required/left slices figures
    else:
        if pizzeria[N][M] != maxValue:                      # Inorder to avoid unnecessary later redundant call with the same pizza, if pizza is one to be the largest contributor of slices
            findPizzas(N-1, M)                              # If pizza is not largest slices contributor then step down to find the other next major contributor down in herirachy


M,N = map(int, input().split())                             # Fetch Values : M - max slices to order, N - total number of pizza
slicesCount = list(map(int, input().split()))               # get slices for N Pizza
pizzeria = []                                               # To store memoized values for given pizza & given desired slice at moment
selectedPizza = []                                          # List of pizza selected to fulfill the order, contains the number of pizza starting from 1, 2, ...N
possibleWays = []                                           # Total Number of Possible Ways to achieve the max slices
# tracked = []

# preparing the pizzeria matrix that give info about how much max slices can be possible with available pizza's at moment
for i in range(N+1):
        pizzeria.append([0 if i==0 or j==0 else max(pizzeria[i-1][j], slicesCount[i-1] + pizzeria[i-1][j-slicesCount[i-1]]) if slicesCount[i-1]<=j else pizzeria[i-1][j] for j in range(M+1) ])

print()
for i in range(N):
    print(f'{i}  ', end='')
print()

maxValue = pizzeria[N][M]                                   # Rightmost element in last row will be our interest to find about
while True:
    if pizzeria[N][M] != maxValue:                          # Find all possible solution for M slices among N pizza's
        break
    findPizzas(N, M)                                        # find solution for Nth pizza with slicesCount[N-1] slices
    if len(selectedPizza) != 0:
        possibleWays.append(selectedPizza)
        selectedPizza = []                                  # Go for next possible solution
    N -= 1

# print(len(selectedPizza),' '.join(map(str, sorted(selectedPizza))),sep='\n')
# print(sum([slicesCount[i] for i in selectedPizza]))

print("Possible Solutions (stating pizza number starting from 1...N ): ")
for i in possibleWays:
    print(i, sum(map(lambda i: slicesCount[i-1], i)))       # print each solution with sum of slices at the end inorder to verify the validity

print("Possible efficacious solutions (stating pizza number starting from 1...N ): ")
minLength = len(min(possibleWays, key=len))                 # find the solutuion with minimum pizza count fulfilling slices requirement

# Efficient solution i.e minimum pizza and max slices
efficientWays = [i for i in possibleWays if len(i) == minLength]
for i in efficientWays:
    print(i, sum(map(lambda i: slicesCount[i-1], i)))       # print each solution with sum of slices at the end inorder to verify the validity

## Theory - Notes
Pizzeria - DP Approach :

aim : To select pizza inorder to fulfill slices requirement, on a constraint that total slices from all pizza must not exceed the Required Slices count

solution : 2 solution can be possible i.e
           \
		    -> 1) Possible solutions : That include all possible solutions
		       2) Efficacious solutions : includes solution from possible solutions that possess minimal pizza & max slices count ( not greater than demanded slices )

Example :

RequiredSlices = 10
PizzaWithSliceCount : [1, 3, 5, 6, 11]

Ways to get 10 or max near to 10 : [1, 3, 6]  -> Possible solutions
                                   [1, 3, 6]     -> Efficacious solution {i.e with 2 pizza only instead of 3]

 Note : here we can't get 10 slices but we manage to get max number smaller than 10 i.e 9

Approach : Bottom-Up Dynamic Programming

Logic Explanation :

    matrix :- row for pizza & column for demanded slices

	matrix[row][column] = maximum number of slices that can be pacified when demanded [column] slices;
                          with the help of pizza's from set { 0 ... row } at present.

 -> Base Case  :

    1) if slices demanded 0 then, empty set of pizza { [] }

	2) if no pizza given, 0 ways to get the slices demanded

	i.e x=0 or y=0;  matrix[x][y] = 0

 -> Rest Cases :

    For every pizza, we have option to include it or exclude it for given number of slices count

	-> check if slices count of that pizza is less than or equal to slices demanded at instant, if yes then way to include or exclude that pizza can be determined

	   1) Include : eliminate the slices of pizza from demanded value & use sub-problem results memoized earlier

	                slicesCountOfPizzaAtInstant - column number

	   2) Exclude : solution for same demanded slices with sub-problem i.e earlier explored pizza's { matrix[row-1][column] }

	      If pizza slices are greater than what demanded at present, then we can't consider that pizza, so solution will be without accounting that pizza


  -> Equations :

     ( row = i, column = j )


                           0                                             | if i=0                   // With 0 pizza i.e no slices we can't get any slices
	                   0     					 | if j=0           		// When 0 slices are demanded then we don't require any pizza
	matrix[i][j] =				                         |
	                   sliceCount[i] + matrix[i-1][j-sliceCount[i]]  | if sliceCount[i] <= j    // Include the pizza
					                                 |
		           matrix[i-1][j]         			 | if sliceCount[i] > j     // Exclude the pizza

	Matrix representation of above example :

	Example :

		RequiredSlices = 11
		PizzaWithSliceCount : [1, 3, 5, 6, 11]

		             DemandedSlices
	                           j

                      		   0  1  2  3  4  5  6  7  8  9  10

		Slices Pizza  i    0  0  0  0  0  0  0  0  0  0  0  0

                       1           1  0  1  1  1  1  1  1  1  1  1  1

                       3           2  0  1  1  3  4  4  4  4  4  4  4

                       5           3  0  1  1  3  4  5  6  6  8  9  9

		       6           4  0  1  1  3  4  5  6  7  8  9  10

 		      11           5  0  1  1  3  4  5  6  7  8  9  10


	-> BackTracking :

	   start from Right-Most Bottom of Matrix

	   2 type of back tracking :

	   1) any Possible solution :

	      s1 - Go Up ^ until repeat & then choose that pizza i.e when matrix[i][j] != matrix[i-1][j]

		  s2 - subtract selected pizza slices from demanded i.e j - slice[i] & search new demanded value in above row i.e i-1

		       next serach become - matrix[i-1][j-slice[i]]

		  s3 - repeat s1 & s2

		  So transition would be only in 2 direction i.e UP (^)  & LEFT ( <- )
	# M - max pizza's slices
	# N - number of pizza
	M,N = map(int, input().split())
	#Slices Count for each pizza
	slicesCount = list(map(int, input().split()))
	#To store memoized values for given pizza & given desired slice at moment
	pizzeria = []
	# List of pizza selected to fulfill the order
	selectedPizza = []
	#Memoization, (DP)
	for i in range(N+1):
	pizzeria.append([0 if i==0 or j==0 else max(pizzeria[i-1][j], slicesCount[i-1] + pizzeria[i-1][j-slicesCount[i-1]]) if slicesCount[i-1]<=j else pizzeria[i-1][j] for j in range(M+1) ])
	#BackTracking to get minimum pizz with max slices, fulfilling demand as effectively as possible
	while True:
	if N==0 or M==0:
	break
	while slicesCount[N-1] > pizzeria[N][M] :
	N -= 1
	if N == 0:
	break
	while True:
	if pizzeria[N-1][pizzeria[N][M] - slicesCount[N-1]] == pizzeria[N][M] - slicesCount[N-1]:
	break
	else:
	N -= 1
	if N == 0:
	break
	selectedPizza.append(N-1)
	M = pizzeria[N][M] - slicesCount[N-1]
	N -= 1
	#Output
	print(len(selectedPizza),' '.join(map(str, sorted(selectedPizza))),sep='\n')

	### Extra....... Explanation
	# ( Smaple input ) :
	# 26 6
	# 1 5 8 13 20 25
	# ( Smaple Ouptput ):
	# 2
	# 0 5
	### i.e 1st pizza(1 slices) & 6th pizza(25 slices) can be one of the solution
	def findPizzas(N, M):
	'''
	find whether to include pizza at given number row N in pizzeria matrix ( with given Slices count i.e sliceCount[N-1] ) for M slices in solution
	{ find contributing pizza from pizza ID lying inside (1 to N) so that M slices or max count less than M can be attained if possible
	pizza Id for each pizza is rowNumber on which pizza is resting in pizzeria matrix }
	'''
	if N==0 or M==0:
	return
	# It's not going to be contributing, since its value after adding makes greater value than what we desired
	while slicesCount[N-1] > pizzeria[N][M] :
	N -= 1
	if N == 0:
	return
	# Check if this pizza can be included as contributor
	if pizzeria[N-1][pizzeria[N][M] - slicesCount[N-1]] == pizzeria[N][M] - slicesCount[N-1]:
	selectedPizza.append(N) # Select Current Pizza
	findPizzas(N-1,pizzeria[N][M] - slicesCount[N-1]) # Go down to find which pizza can fullfill the required/left slices figures
	else:
	if pizzeria[N][M] != maxValue: # Inorder to avoid unnecessary later redundant call with the same pizza, if pizza is one to be the largest contributor of slices
	findPizzas(N-1, M) # If pizza is not largest slices contributor then step down to find the other next major contributor down in herirachy

	M,N = map(int, input().split()) # Fetch Values : M - max slices to order, N - total number of pizza
	slicesCount = list(map(int, input().split())) # get slices for N Pizza
	pizzeria = [] # To store memoized values for given pizza & given desired slice at moment
	selectedPizza = [] # List of pizza selected to fulfill the order, contains the number of pizza starting from 1, 2, ...N
	possibleWays = [] # Total Number of Possible Ways to achieve the max slices

	# preparing the pizzeria matrix that give info about how much max slices can be possible with available pizza's at moment
	for i in range(N+1):
	pizzeria.append([0 if i==0 or j==0 else max(pizzeria[i-1][j], slicesCount[i-1] + pizzeria[i-1][j-slicesCount[i-1]]) if slicesCount[i-1]<=j else pizzeria[i-1][j] for j in range(M+1) ])

	maxValue = pizzeria[N][M] # Rightmost element in last row will be our interest to find about
	while True:
	if pizzeria[N][M] != maxValue: # Find all possible solution for M slices among N pizza's
	break
	findPizzas(N, M) # find solution for Nth pizza with slicesCount[N-1] slices
	if len(selectedPizza) != 0:
	possibleWays.append(selectedPizza)
	selectedPizza = [] # Go for next possible solution
	N -= 1

	print("Possible Solutions (stating pizza number starting from 1...N ): ")
	for i in possibleWays:
	print(i, sum(map(lambda i: slicesCount[i-1], i))) # print each solution with sum of slices at the end inorder to verify the validity

	print("Possible efficacious solutions (stating pizza number starting from 1...N ): ")
	minLength = len(min(possibleWays, key=len)) # find the solutuion with minimum pizza count fulfilling slices requirement

	# Efficient solution i.e minimum pizza and max slices
	efficientWays = [i for i in possibleWays if len(i) == minLength]
	for i in efficientWays:
	print(i, sum(map(lambda i: slicesCount[i-1], i))) # print each solution with sum of slices at the end inorder to verify the validity

	###Extra...Sample
	## Input:
	# 26 6
	# 1 5 6 8 13 20 25
	## Output:
	# Possible solutions (stating pizza number starting from 1...N ) :
	# [7, 1] 26
	# [6, 3] 26
	# [5, 4, 2] 26
	# Explaination sol_1 : 7th(25 slices) & 1st(1 slice)
	# sol_2 : 3rd(6 slices) & 6th(20 slices)
	# sol_3 : 5th(13 slices), 4th(8 slices) & 2nd(5 slices)
	# Possible efficacious solutions (stating pizza number starting from 1...N ):
	# [7, 1] 26
	# [6, 3] 26
	# Explanation sol_1 & sol_3 from above as they both possess minimum pizza i.e 2 pizza only
	##
	###Over
	import logging

	### Globals-------------------------------------------------------------------------------------------------------------------
	pizzeria = [] # To store memoized values for given pizza & given desired slice at moment
	selectedPizza = [] # List of pizza selected to fulfill the order, contains the number of pizza starting from 1, 2, ...N
	possibleWays = [] # Total Number of Possible Ways to achieve the max slices

	### Functions-------------------------------------------------------------------------------------------------------------------
	def findPizzas(N, M):
	'''
	find whether to include pizza at given number row N in pizzeria matrix ( with given Slices count i.e sliceCount[N-1] ) for M slices in solution
	{ find contributing pizza from pizza ID lying inside (1 to N) so that M slices or max count less than M can be attained if possible
	pizza Id for each pizza is rowNumber on which pizza is resting in pizzeria matrix }
	'''
	if N==0 or M==0:
	return

	# It's not going to be contributing, since its value after adding makes greater value than what we desired
	while slicesCount[N] > pizzeria[N][M] :
	N -= 1
	if N == 0:
	return

	leftOver = pizzeria[N][M] - slicesCount[N] # left required slices after removing slices from current pizza (N)

	# Check if this pizza (N) can be included as contributor
	if pizzeria[N-1][leftOver] == leftOver:
	selectedPizza.append(N) # Select Current Pizza
	logging.info(f'Pizza number : {N}, slices : {slicesCount[N]}, demand : {M}')
	findPizzas(N-1, leftOver) # Go down to find which pizza can fullfill the required/left slices figures
	else:
	if pizzeria[N][M] != maxValue: # Inorder to avoid unnecessary later redundant call with the same pizza, if pizza is one to be the largest contributor of slices
	findPizzas(N-1, M) # If pizza is not largest slices contributor then step down to find the other next major contributor down in herirachy

	### Main Code ------------------------------------------------------------------------------------------------------------

	showLogs = input('\nDo you wanna display logs (for tracking) ? { y/n } : ')

	while showLogs not in ('y', 'Y', 'n', 'N'):
	showLogs = input('invalid input ! try again : ')

	if showLogs in ('y', 'Y'):
	print('\n------------------------------------------------ Logs -----------------------------------------------------------------')
	logging.basicConfig(level=logging.DEBUG)
	else:
	logging.disable(logging.CRITICAL)

	logging.info('*Task Started* \n')
	logging.info('=> Fetching inputs ... ')

	# Fetch Values : M - max slices to order, N - total number of pizza
	M,N = map(int, input('\nEnter number of Slices to Order & number of pizza available (seperated by spaces): ').strip().split()[:2])
	# get slices for N Pizza
	slicesCount = [0, *list(map(int, input('Enter Slices for each pizza in Non-Decreasing order (seperated by pizza) ').strip().split()[:N]))]
	# preparing the pizzeria matrix that give info about how much max slices can be possible with available pizza's at moment
	for i in range(N+1):
	pizzeria.append([0 if i==0 or j==0 else max(pizzeria[i-1][j], slicesCount[i] + pizzeria[i-1][j-slicesCount[i]]) if slicesCount[i]<=j else pizzeria[i-1][j] for j in range(M+1)])

	maxValue = pizzeria[N][M] # Rightmost element in last row will be our interest to find about
	while True:
	if pizzeria[N][M] != maxValue: # Find all possible solution for M slices among N pizza's
	break
	if slicesCount[N] <= pizzeria[N][M]:
	logging.info(f'Backtracking for pizza - {N} --------')
	findPizzas(N, M) # find solution for Nth pizza with slicesCount[N] slices
	if any(selectedPizza):
	possibleWays.append(selectedPizza)
	selectedPizza = [] # Go for next possible solution
	N -= 1

	if showLogs in ('y', 'Y'):
	print('\n---------------------------------------------- Logs Over ---------------------------------------------------------------')

	print("\nPossible Solutions (stating pizza number starting from 1...N ): ")
	for i in possibleWays:
	print(i, sum(map(lambda i: slicesCount[i], i))) # print each solution with sum of slices at the end inorder to verify the validity

	minLength = len(min(possibleWays, key=len)) # find the solutuion with minimum pizza count fulfilling slices requirement
	efficientWays = list(filter(lambda way: len(way) == minLength, possibleWays)) # Efficient solution i.e minimum pizza and max slices

	print("Possible efficacious solutions (stating pizza number starting from 1...N ): ")
	for i in efficientWays:
	print(i, sum(map(lambda i: slicesCount[i], i))) # print each solution with sum of slices at the end inorder to verify the validity
	Pizzeria - DP Approach :

	aim : To select pizza inorder to fulfill slices requirement, on a constraint that total slices from all pizza must not exceed the Required Slices count

	solution : 2 solution can be possible i.e
	\
	-> 1) Possible solutions : That include all possible solutions
	2) Efficacious solutions : includes solution from possible solutions that possess minimal pizza & max slices count ( not greater than demanded slices )

	Example :

	RequiredSlices = 10
	PizzaWithSliceCount : [1, 3, 5, 6, 11]

	Ways to get 10 or max near to 10 : [1, 3, 6] -> Possible solutions
	[1, 3, 6] -> Efficacious solution {i.e with 2 pizza only instead of 3]

	Note : here we can't get 10 slices but we manage to get max number smaller than 10 i.e 9

	Approach : Bottom-Up Dynamic Programming

	Logic Explanation :

	matrix :- row for pizza & column for demanded slices

	matrix[row][column] = maximum number of slices that can be pacified when demanded [column] slices;
	with the help of pizza's from set { 0 ... row } at present.

	-> Base Case :

	1) if slices demanded 0 then, empty set of pizza { [] }

	2) if no pizza given, 0 ways to get the slices demanded

	i.e x=0 or y=0; matrix[x][y] = 0

	-> Rest Cases :

	For every pizza, we have option to include it or exclude it for given number of slices count

	-> check if slices count of that pizza is less than or equal to slices demanded at instant, if yes then way to include or exclude that pizza can be determined

	1) Include : eliminate the slices of pizza from demanded value & use sub-problem results memoized earlier

	slicesCountOfPizzaAtInstant - column number

	2) Exclude : solution for same demanded slices with sub-problem i.e earlier explored pizza's { matrix[row-1][column] }

	If pizza slices are greater than what demanded at present, then we can't consider that pizza, so solution will be without accounting that pizza


	-> Equations :

	( row = i, column = j )


	0 \| if i=0 // With 0 pizza i.e no slices we can't get any slices
	0 \| if j=0 // When 0 slices are demanded then we don't require any pizza
	matrix[i][j] = \|
	sliceCount[i] + matrix[i-1][j-sliceCount[i]] \| if sliceCount[i] <= j // Include the pizza
	\|
	matrix[i-1][j] \| if sliceCount[i] > j // Exclude the pizza

	Matrix representation of above example :

	Example :

	RequiredSlices = 11
	PizzaWithSliceCount : [1, 3, 5, 6, 11]

	DemandedSlices
	j

	0 1 2 3 4 5 6 7 8 9 10

	Slices Pizza i 0 0 0 0 0 0 0 0 0 0 0 0

	1 1 0 1 1 1 1 1 1 1 1 1 1

	3 2 0 1 1 3 4 4 4 4 4 4 4

	5 3 0 1 1 3 4 5 6 6 8 9 9

	6 4 0 1 1 3 4 5 6 7 8 9 10

	11 5 0 1 1 3 4 5 6 7 8 9 10


	-> BackTracking :

	start from Right-Most Bottom of Matrix

	2 type of back tracking :

	1) any Possible solution :

	s1 - Go Up ^ until repeat & then choose that pizza i.e when matrix[i][j] != matrix[i-1][j]

	s2 - subtract selected pizza slices from demanded i.e j - slice[i] & search new demanded value in above row i.e i-1

	next serach become - matrix[i-1][j-slice[i]]

	s3 - repeat s1 & s2

	So transition would be only in 2 direction i.e UP (^) & LEFT ( <- )