// C++ program to find minimum cost to get exactly // W Kg with given packets #include   #define INF 1000000 using namespace std; // cost[] initial cost array including unavailable packet // W capacity of bag int MinimumCost(int cost[] int n int W) {  // val[] and wt[] arrays  // val[] array to store cost of 'i' kg packet of orange  // wt[] array weight of packet of orange  vector<int> val wt;  // 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  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];  // fill 0th row with infinity  for (int i=0; i<=W; i++)  min_cost[0][i] = INF;  // fill 0'th column with 0  for (int i=1; i<=n; i++)  min_cost[i][0] = 0;  // now check for each weight one by one and fill the  // matrix according to the condition  for (int i=1; i<=n; i++)  {  for (int j=1; j<=W; j++)  {  // wt[i-1]>j means capacity of bag is  // less than weight of item  if (wt[i-1] > j)  min_cost[i][j] = min_cost[i-1][j];  // here we check we get minimum cost either  // by including it or excluding it  else  min_cost[i][j] = min(min_cost[i-1][j]  min_cost[i][j-wt[i-1]] + val[i-1]);  }  }  // exactly weight W can not be made by given weights  return (min_cost[n][W]==INF)? -1: min_cost[n][W]; } // Driver program to run the test case 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; } 

// Java Code for Minimum cost to // fill given weight in a bag import java.util.*; class GFG {    // cost[] initial cost array including   // unavailable packet W capacity of bag  public static int MinimumCost(int cost[] int n   int W)  {  // val[] and wt[] arrays  // val[] array to store cost of 'i' kg   // packet of orange wt[] array weight of   // packet of orange  Vector<Integer> val = new Vector<Integer>();  Vector<Integer> wt = new Vector<Integer>();    // 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  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];    // fill 0th row with infinity  for (int i = 0; i <= W; i++)  min_cost[0][i] = Integer.MAX_VALUE;    // fill 0'th column with 0  for (int i = 1; i <= n; i++)  min_cost[i][0] = 0;    // now check for each weight one by one and  // fill the matrix according to the condition  for (int i = 1; i <= n; i++)  {  for (int j = 1; j <= W; j++)  {  // wt[i-1]>j means capacity of bag is  // less than weight of item  if (wt.get(i-1) > j)  min_cost[i][j] = min_cost[i-1][j];    // here we check we get minimum cost   // either by including it or excluding  // it  else  min_cost[i][j] = Math.min(min_cost[i-1][j]  min_cost[i][j-wt.get(i-1)] +   val.get(i-1));  }  }    // exactly weight W can not be made by   // given weights  return (min_cost[n][W] == Integer.MAX_VALUE)? -1:   min_cost[n][W];  }    /* Driver program to test above function */  public static void main(String[] args)   {  int cost[] = {1 2 3 4 5} W = 5;  int n = cost.length;    System.out.println(MinimumCost(cost n W));  } } // This code is contributed by Arnav Kr. Mandal. 

# Python program to find minimum cost to get exactly # W Kg with given packets INF = 1000000 # cost[] initial cost array including unavailable packet # W capacity of bag def MinimumCost(cost n W): # val[] and wt[] arrays # val[] array to store cost of 'i' kg packet of orange  # wt[] array weight of packet of orange val = list() wt= list() # 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. size = 0 for i in range(n): if (cost[i] != -1): val.append(cost[i]) wt.append(i+1) size += 1 n = size min_cost = [[0 for i in range(W+1)] for j in range(n+1)] # fill 0th row with infinity for i in range(W+1): min_cost[0][i] = INF # fill 0th column with 0 for i in range(1 n+1): min_cost[i][0] = 0 # now check for each weight one by one and fill the # matrix according to the condition for i in range(1 n+1): for j in range(1 W+1): # wt[i-1]>j means capacity of bag is # less than weight of item if (wt[i-1] > j): min_cost[i][j] = min_cost[i-1][j] # here we check we get minimum cost either # by including it or excluding it else: min_cost[i][j] = min(min_cost[i-1][j] min_cost[i][j-wt[i-1]] + val[i-1]) # exactly weight W can not be made by given weights if(min_cost[n][W] == INF): return -1 else: return min_cost[n][W] # Driver program to run the test case cost = [1 2 3 4 5] W = 5 n = len(cost) print(MinimumCost(cost n W)) # This code is contributed by Soumen Ghosh. 

// C# Code for Minimum cost to  // fill given weight in a bag  using System; using System.Collections.Generic; class GFG {     // cost[] initial cost array including   // unavailable packet W capacity of bag   public static int MinimumCost(int []cost int n   int W)   {   // val[] and wt[] arrays   // val[] array to store cost of 'i' kg   // packet of orange wt[] array weight of   // packet of orange   List<int> val = new List<int>();   List<int> wt = new List<int>();     // 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   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+1W+1];     // fill 0th row with infinity   for (int i = 0; i <= W; i++)   min_cost[0i] = int.MaxValue;     // fill 0'th column with 0   for (int i = 1; i <= n; i++)   min_cost[i0] = 0;     // now check for each weight one by one and   // fill the matrix according to the condition   for (int i = 1; i <= n; i++)   {   for (int j = 1; j <= W; j++)   {   // wt[i-1]>j means capacity of bag is   // less than weight of item   if (wt[i-1] > j)   min_cost[ij] = min_cost[i-1j];     // here we check we get minimum cost   // either by including it or excluding   // it   else  min_cost[ij] = Math.Min(min_cost[i-1j]   min_cost[ij-wt[i-1]] + val[i-1]);   }   }     // exactly weight W can not be made by   // given weights   return (min_cost[nW] == int.MaxValue )? -1: min_cost[nW];   }     /* Driver program to test above function */  public static void Main()  {   int []cost = {1 2 3 4 5};  int W = 5;   int n = cost.Length;     Console.WriteLine(MinimumCost(cost n W));   }  }  // This code is contributed by Ryuga  

 // PHP program to find minimum cost to  // get exactly W Kg with given packets $INF = 1000000; // cost[] initial cost array including  // unavailable packet W capacity of bag function MinimumCost(&$cost $n $W) { global $INF; // val[] and wt[] arrays // val[] array to store cost of 'i'  // kg packet of orange // wt[] array weight of packet of orange $val = array(); $wt = array(); // 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 $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)); // fill 0th row with infinity for ($i = 0; $i <= $W; $i++) $min_cost[0][$i] = $INF; // fill 0'th column with 0 for ($i = 1; $i <= $n; $i++) $min_cost[$i][0] = 0; // now check for each weight one by  // one and fill the matrix according // to the condition for ($i = 1; $i <= $n; $i++) { for ($j = 1; $j <= $W; $j++) { // wt[i-1]>j means capacity of bag  // is less than weight of item if ($wt[$i - 1] > $j) $min_cost[$i][$j] = $min_cost[$i - 1][$j]; // here we check we get minimum  // cost either by including it  // or excluding it else $min_cost[$i][$j] = min($min_cost[$i - 1][$j] $min_cost[$i][$j - $wt[$i - 1]] + $val[$i - 1]); } } // exactly weight W can not be made  // by given weights if ($min_cost[$n][$W] == $INF) return -1; else return $min_cost[$n][$W]; } // Driver Code $cost = array(1 2 3 4 5); $W = 5; $n = sizeof($cost); echo MinimumCost($cost $n $W); // This code is contributed by ita_c ?> 

<script>  // Javascript program to find minimum cost to get exactly  // W Kg with given packets    let INF = 1000000;    // cost[] initial cost array including unavailable packet  // W capacity of bag  function MinimumCost(cost n W)  {  // val[] and wt[] arrays  // val[] array to store cost of 'i' kg packet of orange  // wt[] array weight of packet of orange  let val = [] wt = [];  // 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  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);  }  // fill 0th row with infinity  for (let i=0; i<=W; i++)  min_cost[0][i] = INF;  // fill 0'th column with 0  for (let i=1; i<=n; i++)  min_cost[i][0] = 0;  // now check for each weight one by one and fill the  // matrix according to the condition  for (let i=1; i<=n; i++)  {  for (let j=1; j<=W; j++)  {  // wt[i-1]>j means capacity of bag is  // less than weight of item  if (wt[i-1] > j)  min_cost[i][j] = min_cost[i-1][j];  // here we check we get minimum cost either  // by including it or excluding it  else  min_cost[i][j] = Math.min(min_cost[i-1][j]  min_cost[i][j-wt[i-1]] + val[i-1]);  }  }  // exactly weight W can not be made by given weights  return (min_cost[n][W]==INF)? -1: min_cost[n][W];  }    // Driver code  let cost = [1 2 3 4 5] W = 5;  let n = cost.length;    document.write(MinimumCost(cost n W));    // This code is contributed by suresh07. </script> 

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

// Java program to find minimum cost to  // get exactly W Kg with given packets import java.util.*; class Main {    /* Returns the best obtainable price for  a rod of length n and price[] as prices   of different pieces */  public static int minCost(int cost[] int n)   {   int dp[] = new int[n + 1];   dp[0] = 0;     // Build the table val[] in bottom up   // manner and return the last entry   // from the table   for (int i = 1; i <= n; i++)   {   int min_cost = Integer.MAX_VALUE;   for (int j = 0; j < i; j++)   if(cost[j]!=-1) {  min_cost = Math.min(min_cost cost[j] + dp[i - j - 1]);   }  dp[i] = min_cost;   }     return dp[n];   }   public static void main(String[] args) {  int cost[] = {10-1-1-1-1};  int W = cost.length;   System.out.print(minCost(cost W));   } } // This code is contributed by divyeshrabadiya07 

# Python3 program to find minimum cost to  # get exactly W Kg with given packets import sys # Returns the best obtainable price for # a rod of length n and price[] as prices  # of different pieces  def minCost(cost n): dp = [0 for i in range(n + 1)] # Build the table val[] in bottom up  # manner and return the last entry  # from the table  for i in range(1 n + 1): min_cost = sys.maxsize for j in range(i): if cost[j]!=-1: min_cost = min(min_cost cost[j] + dp[i - j - 1]) dp[i] = min_cost return dp[n] # Driver code cost = [ 10-1-1-1-1 ] W = len(cost) print(minCost(cost W)) # This code is contributed by rag2127 

// C# program to find minimum cost to  // get exactly W Kg with given packets using System; class GFG {    /* Returns the best obtainable price for  a rod of length n and price[] as prices   of different pieces */  static int minCost(int[] cost int n)   {   int[] dp = new int[n + 1];   dp[0] = 0;     // Build the table val[] in bottom up   // manner and return the last entry   // from the table   for (int i = 1; i <= n; i++)   {   int min_cost = Int32.MaxValue;   for (int j = 0; j < i; j++)   if(cost[j]!=-1)  min_cost = Math.Min(min_cost   cost[j] + dp[i - j - 1]);   dp[i] = min_cost;   }     return dp[n];   }     // Driver code  static void Main() {  int[] cost = {20 10 4 50 100};  int W = cost.Length;   Console.Write(minCost(cost W));   } } // This code is contributed by divyesh072019 

<script>  // Javascript 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 */  function minCost(cost n)  {  let dp = new Array(n+1);  dp[0] = 0;  // Build the table val[] in bottom up  // manner and return the last entry  // from the table  for (let i = 1; i<=n; i++)  {  let min_cost = Number.MAX_VALUE;  for (let j = 0; j < i; j++)  if(j < n)  min_cost = Math.min(min_cost cost[j] + dp[i-j-1]);  dp[i] = min_cost;  }  return dp[n];  }  let cost = [20 10 4 50 100];  let W = cost.length;  document.write(minCost(cost W));   </script> 

// C++ program to find minimum cost to // get exactly W Kg with given packets #include    using namespace std; int helper(vector<int>& cost vector<int>& weight int n  int w vector<vector<int> >& dp) {  // base cases  if (w == 0)  return 0;  if (w < 0 or n <= 0)  return INT_MAX;  if (dp[n][w] != -1)  return dp[n][w];  if (cost[n - 1] < 0)  return dp[n][w]  = min(INT_MAX  helper(cost weight n - 1 w dp));  if (weight[n - 1] <= w) {  return dp[n][w]  = min(cost[n - 1]  + helper(cost weight n  w - weight[n - 1] dp)  helper(cost weight n - 1 w dp));  }  return dp[n][w] = helper(cost weight n - 1 w dp); } int minCost(vector<int>& cost int W) {  int N = cost.size();  // Your code goes here  vector<int> weight(N);  // create the weight array  for (int i = 1; i <= N; i++) {  weight[i - 1] = i;  }  // initialize the dp array  vector<vector<int> > dp(N + 1 vector<int>(W + 1 -1));  int res = helper(cost weight N W dp);  // return -1 if result is MAX  return (res == INT_MAX) ? -1 : res; } /* Driver code */ int main() {  vector<int> cost = { 20 10 4 50 100 };  int W = cost.size();  cout << minCost(cost W);  return 0; } 

// Java program to find minimum cost to // get exactly W Kg with given packets import java.io.*; class GFG {  public static int helper(int cost[] int weight[]  int n int w int dp[][])  {  // base cases  if (w == 0)  return 0;  if (w < 0 || n <= 0)  return Integer.MAX_VALUE;  if (dp[n][w] != -1)  return dp[n][w];  if (cost[n - 1] < 0)  return dp[n][w] = Math.min(  Integer.MAX_VALUE  helper(cost weight n - 1 w dp));  if (weight[n - 1] <= w) {  return dp[n][w] = Math.min(  cost[n - 1]  + helper(cost weight n  w - weight[n - 1] dp)  helper(cost weight n - 1 w dp));  }  return dp[n][w]  = helper(cost weight n - 1 w dp);  }  public static int minCost(int cost[] int W)  {  int N = cost.length;  int weight[] = new int[N];  // create the weight array  for (int i = 1; i <= N; i++) {  weight[i - 1] = i;  }  // initialize the dp array  int dp[][] = new int[N + 1][W + 1];  for (int i = 0; i < N + 1; i++)  for (int j = 0; j < W + 1; j++)  dp[i][j] = -1;  int res = helper(cost weight N W dp);  // return -1 if result is MAX  return (res == Integer.MAX_VALUE) ? -1 : res;  }  // Driver Code  public static void main(String[] args)  {  int cost[] = { 20 10 4 50 100 };  int W = cost.length;  System.out.print(minCost(cost W));  } } // This code is contributed by Rohit Pradhan 

# Python3 program to find minimum cost to # get exactly W Kg with given packets import sys def helper(cost weight n w dp): # base cases if (w == 0): return 0 if (w < 0 or n <= 0): return sys.maxsize if (dp[n][w] != -1): return dp[n][w] if (cost[n - 1] < 0): dp[n][w] = min(sys.maxsize helper(cost weight n - 1 w dp)) return dp[n][w] if (weight[n - 1] <= w): dp[n][w] = min(cost[n - 1] + helper(cost weight n w - weight[n - 1] dp) helper(cost weight n - 1 w dp)) return dp[n][w] dp[n][w] = helper(cost weight n - 1 w dp) return dp[n][w] def minCost(cost W): N = len(cost) weight = [0 for i in range(N)] # create the weight array for i in range(1N + 1): weight[i - 1] = i # initialize the dp array dp = [[-1 for i in range(W + 1)]for j in range(N + 1)] res = helper(cost weight N W dp) # return -1 if result is MAX return -1 if(res == sys.maxsize) else res # Driver code  cost = [ 20 10 4 50 100 ] W = len(cost) print(minCost(cost W)) # This code is contributed by shinjanpatra 

// C# program to find minimum cost to // get exactly W Kg with given packets using System; class GFG  {  static int helper(int[] cost int[] weight   int n int w int[] dp)  {  // base cases  if (w == 0)  return 0;  if (w < 0 || n <= 0)  return Int32.MaxValue;  if (dp[nw] != -1)  return dp[nw];  if (cost[n - 1] < 0)  return dp[nw] = Math.Min(  Int32.MaxValue  helper(cost weight n - 1 w dp));  if (weight[n - 1] <= w)   {  return dp[nw] = Math.Min(  cost[n - 1]  + helper(cost weight n  w - weight[n - 1] dp)  helper(cost weight n - 1 w dp));  }  return dp[nw]  = helper(cost weight n - 1 w dp);  }  static int minCost(int[] cost int W)  {  int N = cost.Length;  int[] weight = new int[N];  // create the weight array  for (int i = 1; i <= N; i++)   {  weight[i - 1] = i;  }  // initialize the dp array  int[] dp = new int[N + 1 W + 1];  for (int i = 0; i < N + 1; i++)  for (int j = 0; j < W + 1; j++)  dp[ij] = -1;  int res = helper(cost weight N W dp);  // return -1 if result is MAX  return (res == Int32.MaxValue) ? -1 : res;  }  // Driver Code  static public void Main()  {  int[] cost = { 20 10 4 50 100 };  int W = cost.Length;  Console.Write(minCost(cost W));  } } // This code is contributed by kothavvsaakash 

<script> // JavaScript program to find minimum cost to // get exactly W Kg with given packets function helper(cost weight n w dp) {  // base cases  if (w == 0)  return 0;  if (w < 0 || n <= 0)  return Number.MAX_VALUE;  if (dp[n][w] != -1)  return dp[n][w];  if (cost[n - 1] < 0)  return dp[n][w]  = Math.min(Number.MAX_VALUE  helper(cost weight n - 1 w dp));  if (weight[n - 1] <= w) {  return dp[n][w]  = Math.min(cost[n - 1]  + helper(cost weight n  w - weight[n - 1] dp)  helper(cost weight n - 1 w dp));  }  return dp[n][w] = helper(cost weight n - 1 w dp); } function minCost(costW) {  let N = cost.length;  // Your code goes here  let weight = new Array(N);  // create the weight array  for (let i = 1; i <= N; i++) {  weight[i - 1] = i;  }  // initialize the dp array  let dp = new Array(N + 1).fill(-1).map(()=>new Array(W + 1).fill(-1));  let res = helper(cost weight N W dp);  // return -1 if result is MAX  return (res == Number.MAX_VALUE) ? -1 : res; } /* Driver code */ let cost = [ 20 10 4 50 100 ]; let W = cost.length; document.write(minCost(cost W)'
'); // This code is contributed by shinjanpatra </script>