Minimum cost to fill given weight in a bag | Python program to find minimum cost to get exactly W Kg with given packets ; cost [ ] initial cost array including unavailable packet W capacity of bag ; val [ ] and wt [ ] arrays val [ ] array to store cost of ' i ' kg packet of orange wt [ ] array weight of packet of orange ; traverse the original cost [ ] array and skip unavailable packets and make val [ ] and wt [ ] array . size variable tells the available number of distinct weighted packets . ; fill 0 th row with infinity ; fill 0 th column with 0 ; now check for each weight one by one and fill the matrix according to the condition ; wt [ i - 1 ] > j means capacity of bag is less than weight of item ; here we check we get minimum cost either by including it or excluding it ; exactly weight W can not be made by given weights ; Driver program to run the test case
INF = 1000000 NEW_LINE def MinimumCost ( cost , n , W ) : NEW_LINE INDENT val = list ( ) NEW_LINE wt = list ( ) NEW_LINE size = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( cost [ i ] != - 1 ) : NEW_LINE INDENT val . append ( cost [ i ] ) NEW_LINE wt . append ( i + 1 ) NEW_LINE size += 1 NEW_LINE DEDENT DEDENT n = size NEW_LINE min_cost = [ [ 0 for i in range ( W + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( W + 1 ) : NEW_LINE INDENT min_cost [ 0 ] [ i ] = INF NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT min_cost [ i ] [ 0 ] = 0 NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , W + 1 ) : NEW_LINE INDENT if ( wt [ i - 1 ] > j ) : NEW_LINE INDENT min_cost [ i ] [ j ] = min_cost [ i - 1 ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT min_cost [ i ] [ j ] = min ( min_cost [ i - 1 ] [ j ] , min_cost [ i ] [ j - wt [ i - 1 ] ] + val [ i - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT if ( min_cost [ n ] [ W ] == INF ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return min_cost [ n ] [ W ] NEW_LINE DEDENT DEDENT cost = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE W = 5 NEW_LINE n = len ( cost ) NEW_LINE print ( MinimumCost ( cost , n , W ) ) NEW_LINE