Coût minimum pour remplir un poids donné dans un sac
Vous recevez un sac de taille W kg et vous recevez les coûts des paquets de différents poids d'oranges dans le tableau coût[] où coût[i] est essentiellement le coût de 'je' kg paquet d'oranges. Où cost[i] = -1 signifie que 'je' Le paquet de kg d'orange n'est pas disponible
Trouvez le coût total minimum pour acheter exactement W kg d'oranges et s'il n'est pas possible d'acheter exactement W kg d'oranges, imprimez -1. On peut supposer qu’il existe une quantité infinie de tous les types de paquets disponibles.
Note: le tableau commence à partir de l’index 1.
Exemples :
Input : W = 5 cost[] = {20 10 4 50 100} Output : 14 We can choose two oranges to minimize cost. First orange of 2Kg and cost 10. Second orange of 3Kg and cost 4. Input : W = 5 cost[] = {1 10 4 50 100} Output : 5 We can choose five oranges of weight 1 kg. Input : W = 5 cost[] = {1 2 3 4 5} Output : 5 Costs of 1 2 3 4 and 5 kg packets are 1 2 3 4 and 5 Rs respectively. We choose packet of 5kg having cost 5 for minimum cost to get 5Kg oranges. Input : W = 5 cost[] = {-1 -1 4 5 -1} Output : -1 Packets of size 1 2 and 5 kg are unavailable because they have cost -1. Cost of 3 kg packet is 4 Rs and of 4 kg is 5 Rs. Here we have only weights 3 and 4 so by using these two we can not make exactly W kg weight therefore answer is -1. Recommended Practice Coût minimum pour remplir un poids donné dans un sac Essayez-le ! Méthode 1 :
Ce problème peut être réduit à Sac à dos illimité k. Ainsi, dans le tableau des coûts, nous ignorons d'abord les paquets qui ne sont pas disponibles, c'est-à-dire : le coût est -1, puis parcourez le tableau de coûts et créez deux tableaux val[] pour stocker le coût de 'je' kg de paquet d'orange et wt[] pour stocker le poids du paquet correspondant. Supposons que cost[i] = 50 donc le poids du paquet sera i et le coût sera de 50.
Algorithme :
- Créez la matrice min_cost[n+1][W+1] où n est le nombre de paquets d'orange pondérés distincts et W est la capacité maximale du sac.
- Initialisez la 0ème ligne avec INF (infini) et la 0ème colonne avec 0.
- Maintenant, remplissez la matrice
- si wt[i-1] > j alors min_cost[i][j] = min_cost[i-1][j] ;
- si poids[i-1] <= j then min_cost[i][j] = min(min_cost[i-1][j] val[i-1] + min_cost[i][j-wt[i-1]]);
- Si min_cost[n][W]==INF alors la sortie sera -1 car cela signifie que nous ne pouvons pas créer de poids W en utilisant ces poids, sinon la sortie sera min_cost[n][W] .
Vous trouverez ci-dessous l'implémentation de l'algorithme ci-dessus :
C++ // 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 // 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.
Python3 # 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# // 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 + 1 W + 1 ]; // fill 0th row with infinity for ( int i = 0 ; i <= W ; i ++ ) min_cost [ 0 i ] = int . MaxValue ; // 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 ] = 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 ] == int . MaxValue ) ? - 1 : min_cost [ n W ]; } /* 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 // 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 ?>
JavaScript < 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>
Sortir
5
Complexité temporelle : O (n * w)
Espace auxiliaire : O (n * w)
Solution optimisée pour l'espace Si nous examinons ce problème de plus près, nous remarquerons qu'il s'agit d'une variante de Problème de coupe de tige . Au lieu de faire de la maximisation ici, nous devons faire de la minimisation.
C++ // 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 // 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 # 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# // 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
JavaScript < 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>
Sortir
14
Complexité temporelle : SUR 2 )
Espace auxiliaire : SUR)
Approche descendante : Nous pouvons également résoudre le problème en utilisant la mémorisation.
C++ // 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 // 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 # 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 ( 1 N + 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# // 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 [ n w ] != - 1 ) return dp [ n w ]; if ( cost [ n - 1 ] < 0 ) return dp [ n w ] = Math . Min ( Int32 . MaxValue 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 ); } 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 == 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
JavaScript < 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 ( cost W ) { 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>
Sortir
14
Complexité temporelle : O(N*W)
Espace auxiliaire : O(N*W)
Cet article est révisé par l'équipe GeeksForGeeks.
