Minimum cost to fill given weight in a bag | PHP 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
< ? php $ INF = 1000000 ; function MinimumCost ( & $ cost , $ n , $ W ) { global $ INF ; $ val = array ( ) ; $ wt = array ( ) ; $ size = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( $ cost [ $ i ] != -1 ) { array_push ( $ val , $ cost [ $ i ] ) ; array_push ( $ wt , $ i + 1 ) ; $ size ++ ; } } $ n = $ size ; $ min_cost = array_fill ( 0 , $ n + 1 , array_fill ( 0 , $ W + 1 , NULL ) ) ; for ( $ i = 0 ; $ i <= $ W ; $ i ++ ) $ min_cost [ 0 ] [ $ i ] = $ INF ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) $ min_cost [ $ i ] [ 0 ] = 0 ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { for ( $ j = 1 ; $ j <= $ W ; $ j ++ ) { if ( $ wt [ $ i - 1 ] > $ j ) $ min_cost [ $ i ] [ $ j ] = $ min_cost [ $ i - 1 ] [ $ j ] ; else $ min_cost [ $ i ] [ $ j ] = min ( $ min_cost [ $ i - 1 ] [ $ j ] , $ min_cost [ $ i ] [ $ j - $ wt [ $ i - 1 ] ] + $ val [ $ i - 1 ] ) ; } } if ( $ min_cost [ $ n ] [ $ W ] == $ INF ) return -1 ; else return $ min_cost [ $ n ] [ $ W ] ; } $ cost = array ( 1 , 2 , 3 , 4 , 5 ) ; $ W = 5 ; $ n = sizeof ( $ cost ) ; echo MinimumCost ( $ cost , $ n , $ W ) ; ? >