Minimum cost to fill given weight in a bag | C ++ program to find minimum cost to get exactly W Kg with given packets ; Returns the best obtainable price for a rod of length n and price [ ] as prices of different pieces ; Build the table val [ ] in bottom up manner and return the last entry from the table ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minCost ( int cost [ ] , int n ) { int dp [ n + 1 ] ; dp [ 0 ] = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { int min_cost = INT_MAX ; for ( int j = 0 ; j < i ; j ++ ) if ( j < n && cost [ j ] != -1 ) min_cost = min ( min_cost , cost [ j ] + dp [ i - j - 1 ] ) ; dp [ i ] = min_cost ; } return dp [ n ] ; } int main ( ) { int cost [ ] = { 20 , 10 , 4 , 50 , 100 } ; int W = sizeof ( cost ) / sizeof ( cost [ 0 ] ) ; cout << minCost ( cost , W ) ; return 0 ; }