A Space Optimized DP solution for 0 | C # program of a space optimized DP solution for 0 - 1 knapsack problem . ; val [ ] is for storing maximum profit for each weight wt [ ] is for storing weights n number of item W maximum capacity of bag mat [ 2 , W + 1 ] to store final result ; matrix to store final result ; iterate through all items ; one by one traverse each element ; traverse all weights j <= W ; if i is odd that mean till now we have odd number of elements so we store result in 1 th indexed row ; check for each value ; include element ; exclude element ; if i is even that means till now we have even number of elements so we store result in 0 th indexed row ; Return mat [ 0 , W ] if n is odd , else mat [ 1 , W ] ; Driver Code
using System ; class GFG { static int KnapSack ( int [ ] val , int [ ] wt , int n , int W ) { int [ , ] mat = new int [ 2 , W + 1 ] ; int i = 0 ; while ( i < n ) { int j = 0 ; if ( i % 2 != 0 ) { while ( ++ j <= W ) { if ( wt [ i ] <= j ) { mat [ 1 , j ] = Math . Max ( val [ i ] + mat [ 0 , j - wt [ i ] ] , mat [ 0 , j ] ) ; } else { mat [ 1 , j ] = mat [ 0 , j ] ; } } } else { while ( ++ j <= W ) { if ( wt [ i ] <= j ) { mat [ 0 , j ] = Math . Max ( val [ i ] + mat [ 1 , j - wt [ i ] ] , mat [ 1 , j ] ) ; } else { mat [ 0 , j ] = mat [ 1 , j ] ; } } } i ++ ; } return ( n % 2 != 0 ) ? mat [ 0 , W ] : mat [ 1 , W ] ; } public static void Main ( String [ ] args ) { int [ ] val = { 7 , 8 , 4 } ; int [ ] wt = { 3 , 8 , 6 } ; int W = 10 , n = 3 ; Console . WriteLine ( KnapSack ( val , wt , n , W ) ) ; } }