가방에 주어진 무게를 채우는 데 드는 최소 비용
Wkg 크기의 가방이 주어졌고 배열 비용[]에서 다양한 무게의 오렌지 패킷 비용이 제공되었습니다. 비용[i] 기본적으로 비용은 '나' kg 오렌지 패킷. 여기서 cost[i] = -1은 다음을 의미합니다. '나' kg 오렌지 패킷을 사용할 수 없습니다.
정확히 Wkg 오렌지를 구입하는 데 필요한 최소 총 비용을 구하고, 정확히 Wkg 오렌지를 구입하는 것이 불가능하면 -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:
이 문제는 다음과 같이 축소될 수 있습니다. 무한한 배낭 케이. 따라서 비용 배열에서 우리는 먼저 사용할 수 없는 패킷을 무시합니다. 비용은 -1이고 비용 배열을 순회하고 비용을 저장하기 위해 두 개의 배열 val[]을 만듭니다. '나' 오렌지의 kg 패킷과 해당 패킷의 무게를 저장하는 wt[]입니다. cost[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] ;
- 만약 wt[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
시간 복잡도: 오(n*w)
보조 공간: 오(n*w)
공간 최적화 솔루션 이 문제를 자세히 살펴보면 이것이 다음과 같은 변형임을 알 수 있습니다. 로드 절단 문제 . 여기서는 최대화를 수행하는 대신 최소화를 수행해야 합니다.
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 팀에서 검토했습니다.
