Minimum cost to fill given weight in a bag | C ++ 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 program to run the test case
#include <bits/stdc++.h> NEW_LINE #define INF  1000000 NEW_LINE using namespace std ; int MinimumCost ( int cost [ ] , int n , int W ) { vector < int > val , wt ; int size = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( cost [ i ] != -1 ) { val . push_back ( cost [ i ] ) ; wt . push_back ( i + 1 ) ; size ++ ; } } n = size ; int min_cost [ n + 1 ] [ W + 1 ] ; for ( int i = 0 ; i <= W ; i ++ ) min_cost [ 0 ] [ i ] = INF ; 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 ] = 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 ] ; } int main ( ) { int cost [ ] = { 1 , 2 , 3 , 4 , 5 } , W = 5 ; int n = sizeof ( cost ) / sizeof ( cost [ 0 ] ) ; cout << MinimumCost ( cost , n , W ) ; return 0 ; }