Maximum items that can be filled in K Knapsacks of given Capacity |  ; 2 - d array to store states of DP ; 2 - d array to store if a state has been solved ; Vector to store power of variable ' C ' . ; function to compute the states ; Base case ; Checking if a state has been solved ; Setting a state as solved ; Recurrence relation ; Returning the solved state ; Function to initialize global variables and find the initial value of ' R ' ; Resizing the variables ; Variable to store the initial value of R ; Driver Code ; Input array ; number of knapsacks and capacity ; Performing required pre - computation ; finding the required answer
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < vector < int > > dp ; vector < vector < bool > > v ; vector < int > exp_c ; int FindMax ( int i , int r , int w [ ] , int n , int c , int k ) { if ( i >= n ) return 0 ; if ( v [ i ] [ r ] ) return dp [ i ] [ r ] ; v [ i ] [ r ] = 1 ; dp [ i ] [ r ] = FindMax ( i + 1 , r , w , n , c , k ) ; for ( int j = 0 ; j < k ; j ++ ) { int x = ( r / exp_c [ j ] ) % ( c + 1 ) ; if ( x - w [ i ] >= 0 ) dp [ i ] [ r ] = max ( dp [ i ] [ r ] , w [ i ] + FindMax ( i + 1 , r - w [ i ] * exp_c [ j ] , w , n , c , k ) ) ; } return dp [ i ] [ r ] ; } int PreCompute ( int n , int c , int k ) { exp_c . resize ( k ) ; exp_c [ 0 ] = 1 ; for ( int i = 1 ; i < k ; i ++ ) { exp_c [ i ] = ( exp_c [ i - 1 ] * ( c + 1 ) ) ; } dp . resize ( n ) ; for ( int i = 0 ; i < n ; i ++ ) { dp [ i ] . resize ( exp_c [ k - 1 ] * ( c + 1 ) , 0 ) ; } v . resize ( n ) ; for ( int i = 0 ; i < n ; i ++ ) { v [ i ] . resize ( exp_c [ k - 1 ] * ( c + 1 ) , 0 ) ; } int R = 0 ; for ( int i = 0 ; i < k ; i ++ ) { R += exp_c [ i ] * c ; } return R ; } int main ( ) { int w [ ] = { 3 , 8 , 9 } ; int k = 1 , c = 11 ; int n = sizeof ( w ) / sizeof ( int ) ; int r = PreCompute ( n , c , k ) ; cout << FindMax ( 0 , r , w , n , c , k ) ; return 0 ; }