Minimum cost to fill given weight in a bag | C # Code for Minimum cost to fill given weight in a bag ; 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 program to test above function
using System ; using System . Collections . Generic ; class GFG { public static int MinimumCost ( int [ ] cost , int n , int W ) { List < int > val = new List < int > ( ) ; List < int > wt = new List < int > ( ) ; int size = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( cost [ i ] != - 1 ) { val . Add ( cost [ i ] ) ; wt . Add ( i + 1 ) ; size ++ ; } } n = size ; int [ , ] min_cost = new int [ n + 1 , W + 1 ] ; for ( int i = 0 ; i <= W ; i ++ ) min_cost [ 0 , i ] = int . MaxValue ; for ( int i = 1 ; i <= n ; i ++ ) min_cost [ i , 0 ] = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int 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 ] == int . MaxValue ) ? - 1 : min_cost [ n , W ] ; } public static void Main ( ) { int [ ] cost = { 1 , 2 , 3 , 4 , 5 } ; int W = 5 ; int n = cost . Length ; Console . WriteLine ( MinimumCost ( cost , n , W ) ) ; } }