Minimum cost to buy N kilograms of sweet for M persons | Function to find the minimum cost of sweets ; Defining the sweet array ; DP array to store the values ; Since index starts from 1 we reassign the array into sweet ; Assigning base cases for dp array ; At 0 it is free ; Package not available for desirable amount of sweets ; Buying the ' k ' kg package and assigning it to dp array ; If no solution , select from previous k - 1 packages ; If solution does not exist ; Print the solution ; Driver Function ; Calling the desired function
def find ( m , n , adj ) : NEW_LINE INDENT sweet = [ 0 ] * ( n + 1 ) NEW_LINE dp = [ [ [ 0 for i in range ( n + 1 ) ] for i in range ( n + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE sweet [ 0 ] = 0 NEW_LINE for i in range ( 1 , m + 1 ) : NEW_LINE INDENT sweet [ i ] = adj [ i - 1 ] NEW_LINE DEDENT for i in range ( m + 1 ) : NEW_LINE INDENT for k in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] [ k ] = 0 NEW_LINE DEDENT for k in range ( 1 , n + 1 ) : NEW_LINE INDENT dp [ i ] [ k ] [ 0 ] = - 1 NEW_LINE DEDENT DEDENT for i in range ( m + 1 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT for k in range ( 1 , n + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = - 1 NEW_LINE if ( i > 0 and j >= k and sweet [ k ] > 0 and dp [ i - 1 ] [ j - k ] [ k ] != - 1 ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = dp [ i - 1 ] [ j - k ] [ k ] + sweet [ k ] NEW_LINE DEDENT if ( dp [ i ] [ j ] [ k ] == - 1 or ( dp [ i ] [ j ] [ k - 1 ] != - 1 and dp [ i ] [ j ] [ k ] > dp [ i ] [ j ] [ k - 1 ] ) ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = dp [ i ] [ j ] [ k - 1 ] NEW_LINE DEDENT DEDENT DEDENT DEDENT if ( dp [ m ] [ n ] [ n ] == - 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT else : NEW_LINE INDENT return dp [ m ] [ n ] [ n ] NEW_LINE DEDENT DEDENT m = 3 NEW_LINE adj = [ 2 , 1 , 3 , 0 , 4 , 10 ] NEW_LINE n = len ( adj ) NEW_LINE print ( find ( m , n , adj ) ) NEW_LINE