الحد الأدنى من التكلفة لملء الوزن المحدد في الحقيبة
يتم إعطاؤك كيسًا بحجم W كجم ويتم توفير تكاليف الحزم بأوزان مختلفة من البرتقال بتكلفة المصفوفة[] حيث التكلفة[i] هي في الأساس تكلفة 'أنا' كيلو جرام من البرتقال. حيث التكلفة [i] = -1 تعني ذلك 'أنا' علبة كيلو برتقال غير متوفرة
أوجد الحد الأدنى للتكلفة الإجمالية لشراء برتقال بوزن كيلو جرام بالضبط، وإذا لم يكن من الممكن شراء برتقال بوزن كيلو جرام بالضبط، فاطبع -1. يمكن الافتراض أن هناك عرضًا لا نهائيًا لجميع أنواع الحزم المتوفرة.
ملحوظة: تبدأ المصفوفة من الفهرس 1.
أمثلة:
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 الحد الأدنى من التكلفة لملء الوزن المحدد في الحقيبة جربه! الطريقة الأولى:
يمكن تقليل هذه المشكلة إلى كنابساك غير محدود ك. لذا، في مصفوفة التكلفة، نتجاهل أولاً تلك الحزم غير المتوفرة، على سبيل المثال؛ التكلفة هي -1 ثم اجتياز مصفوفة التكلفة وإنشاء مصفوفتين val[] لتخزين تكلفة 'أنا' كجم من البرتقال ووزن [] لتخزين وزن الحزمة المقابلة. لنفترض أن التكلفة [i] = 50، وبالتالي فإن وزن الحزمة سيكون i وستكون التكلفة 50.
الخوارزمية :
- أنشئ مصفوفة min_cost[n+1][W+1] حيث n هو عدد الحزم الموزونة المميزة للبرتقال وW هي السعة القصوى للكيس.
- قم بتهيئة الصف 0 بـ INF (اللانهاية) والعمود 0 بـ 0.
- الآن املأ المصفوفة
- إذا wt[i-1] > j ثم min_cost[i][j] = min_cost[i-1][j] ;
- إذا بالوزن [i-1] <= j then min_cost[i][j] = min(min_cost[i-1][j] val[i-1] + min_cost[i][j-wt[i-1]]);
- إذا كانت min_cost[n][W]==INF فإن الناتج سيكون -1 لأن هذا يعني أننا لا نستطيع جعل الوزن W باستخدام هذه الأوزان وإلا سيكون الناتج min_cost[n][W] .
فيما يلي تنفيذ الخوارزمية المذكورة أعلاه:
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>
الإخراج
5
تعقيد الوقت: يا (ن * ث)
المساحة المساعدة: يا (ن * ث)
الحل الأمثل للمساحة إذا ألقينا نظرة فاحصة على هذه المشكلة قد نلاحظ أن هذا هو الاختلاف مشكلة قطع القضبان . بدلاً من القيام بالتعظيم هنا، نحتاج إلى القيام بالتصغير.
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>
الإخراج
14
تعقيد الوقت: على 2 )
المساحة المساعدة: على)
النهج من أعلى إلى أسفل: يمكننا أيضًا حل المشكلة باستخدام الحفظ.
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>
الإخراج
14
تعقيد الوقت: O(N*W)
المساحة المساعدة: O(N*W)
تمت مراجعة هذه المقالة بواسطة فريق GeeksForGeeks.
