Minimum cost to fill given weight in a bag | Javascript 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 then 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 code
let INF = 1000000 ; function MinimumCost ( cost , n , W ) { let val = [ ] , wt = [ ] ; let size = 0 ; for ( let i = 0 ; i < n ; i ++ ) { if ( cost [ i ] != - 1 ) { val . push ( cost [ i ] ) ; wt . push ( i + 1 ) ; size ++ ; } } n = size ; let min_cost = new Array ( n + 1 ) ; for ( let i = 0 ; i < n + 1 ; i ++ ) { min_cost [ i ] = new Array ( W + 1 ) ; } for ( let i = 0 ; i <= W ; i ++ ) min_cost [ 0 ] [ i ] = INF ; for ( let i = 1 ; i <= n ; i ++ ) min_cost [ i ] [ 0 ] = 0 ; for ( let i = 1 ; i <= n ; i ++ ) { for ( let j = 1 ; j <= W ; j ++ ) { if ( wt [ i - 1 ] > j ) min_cost [ i ] [ j ] = min_cost [ i - 1 ] [ j ] ; else min_cost [ i ] [ j ] = Math . min ( min_cost [ i - 1 ] [ j ] , min_cost [ i ] [ j - wt [ i - 1 ] ] + val [ i - 1 ] ) ; } } return ( min_cost [ n ] [ W ] == INF ) ? - 1 : min_cost [ n ] [ W ] ; } let cost = [ 1 , 2 , 3 , 4 , 5 ] , W = 5 ; let n = cost . length ; document . write ( MinimumCost ( cost , n , W ) ) ;