Given an integer array W[] consisting of weights of the items and some queries consisting of capacity C of knapsack, for each query find maximum weight we can put in the knapsack. Value of C doesn’t exceed a certain integer C_MAX.
Examples:
Input: W[] = {3, 8, 9} q = {11, 10, 4}
Output:
11
9
3
If C = 11: select 3 + 8 = 11
If C = 10: select 9
If C = 4: select 3Input: W[] = {1, 5, 10} q = {6, 14}
Output:
6
11
Its recommended that you go through this article on 0-1 knapsack before attempting this problem.
Naive approach: For each query, we can generate all possible subsets of weight and choose the one that has maximum weight among all those subsets that fits in the knapsack. Thus, answering each query will take exponential time.
Efficient approach: We will optimize answering each query using dynamic programming.
0-1 knapsack is solved using 2-D DP, one state ‘i’ for current index(i.e select or reject) and one for remaining capacity ‘R’.
Recurrence relation is
dp[i][R] = max(arr[i] + dp[i + 1][R – arr[i]], dp[i + 1][R])
We will pre-compute the 2-d array dp[i][C] for every possible value of ‘C’ between 1 to C_MAX in O(C_MAX*i).
Using this, pre-computation we can answer each queries in O(1) time.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define C_MAX 30#define max_arr_len 10using namespace std;// To store states of DPint dp[max_arr_len][C_MAX + 1];// To check if a state has// been solvedbool v[max_arr_len][C_MAX + 1];// Function to compute the statesint findMax(int i, int r, int w[], int n){ // Base case if (r < 0) return INT_MIN; if (i == n) return 0; // Check if a state has // been solved if (v[i][r]) return dp[i][r]; // Setting a state as solved v[i][r] = 1; dp[i][r] = max(w[i] + findMax(i + 1, r - w[i], w, n), findMax(i + 1, r, w, n)); // Returning the solved state return dp[i][r];}// Function to pre-compute the states// dp[0][0], dp[0][1], .., dp[0][C_MAX]void preCompute(int w[], int n){ for (int i = C_MAX; i >= 0; i--) findMax(0, i, w, n);}// Function to answer a query in O(1)int ansQuery(int w){ return dp[0][w];}// Driver codeint main(){ int w[] = { 3, 8, 9 }; int n = sizeof(w) / sizeof(int); // Performing required // pre-computation preCompute(w, n); int queries[] = { 11, 10, 4 }; int q = sizeof(queries) / sizeof(queries[0]); // Perform queries for (int i = 0; i < q; i++) cout << ansQuery(queries[i]) << endl; return 0;} |
Java
// Java implementation of the approachclass GFG{ static int C_MAX = 30; static int max_arr_len = 10; // To store states of DP static int dp [][] = new int [max_arr_len][C_MAX + 1]; // To check if a state has // been solved static boolean v[][]= new boolean [max_arr_len][C_MAX + 1]; // Function to compute the states static int findMax(int i, int r, int w[], int n) { // Base case if (r < 0) return Integer.MIN_VALUE; if (i == n) return 0; // Check if a state has // been solved if (v[i][r]) return dp[i][r]; // Setting a state as solved v[i][r] = true; dp[i][r] = Math.max(w[i] + findMax(i + 1, r - w[i], w, n), findMax(i + 1, r, w, n)); // Returning the solved state return dp[i][r]; } // Function to pre-compute the states // dp[0][0], dp[0][1], .., dp[0][C_MAX] static void preCompute(int w[], int n) { for (int i = C_MAX; i >= 0; i--) findMax(0, i, w, n); } // Function to answer a query in O(1) static int ansQuery(int w) { return dp[0][w]; } // Driver code public static void main (String[] args) { int w[] = new int []{ 3, 8, 9 }; int n = w.length; // Performing required // pre-computation preCompute(w, n); int queries[] = new int [] { 11, 10, 4 }; int q = queries.length; // Perform queries for (int i = 0; i < q; i++) System.out.println(ansQuery(queries[i])); }}// This code is contributed by ihritik |
Python3
# Python3 implementation of the approach import numpy as npimport sysC_MAX = 30max_arr_len = 10# To store states of DP dp = np.zeros((max_arr_len,C_MAX + 1)); # To check if a state has # been solved v = np.zeros((max_arr_len,C_MAX + 1)); INT_MIN = -(sys.maxsize) + 1# Function to compute the states def findMax(i, r, w, n) : # Base case if (r < 0) : return INT_MIN; if (i == n) : return 0; # Check if a state has # been solved if (v[i][r]) : return dp[i][r]; # Setting a state as solved v[i][r] = 1; dp[i][r] = max(w[i] + findMax(i + 1, r - w[i], w, n), findMax(i + 1, r, w, n)); # Returning the solved state return dp[i][r]; # Function to pre-compute the states # dp[0][0], dp[0][1], .., dp[0][C_MAX] def preCompute(w, n) : for i in range(C_MAX, -1, -1) : findMax(0, i, w, n); # Function to answer a query in O(1) def ansQuery(w) : return dp[0][w]; # Driver code if __name__ == "__main__" : w = [ 3, 8, 9 ]; n = len(w) # Performing required # pre-computation preCompute(w, n); queries = [ 11, 10, 4 ]; q = len(queries) # Perform queries for i in range(q) : print(ansQuery(queries[i]));# This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System;class GFG {static int C_MAX = 30; static int max_arr_len = 10; // To store states of DP static int[,] dp = new int [max_arr_len, C_MAX + 1]; // To check if a state has // been solved static bool[,] v = new bool [max_arr_len, C_MAX + 1]; // Function to compute the states static int findMax(int i, int r, int[] w, int n) { // Base case if (r < 0) return Int32.MaxValue; if (i == n) return 0; // Check if a state has // been solved if (v[i, r]) return dp[i, r]; // Setting a state as solved v[i, r] = true; dp[i, r] = Math.Max(w[i] + findMax(i + 1, r - w[i], w, n), findMax(i + 1, r, w, n)); // Returning the solved state return dp[i, r]; } // Function to pre-compute the states // dp[0][0], dp[0][1], .., dp[0][C_MAX] static void preCompute(int[] w, int n) { for (int i = C_MAX; i >= 0; i--) findMax(0, i, w, n); } // Function to answer a query in O(1) static int ansQuery(int w) { return dp[0, w]; } // Driver code public static void Main() { int[] w= { 3, 8, 9 }; int n = w.Length; // Performing required // pre-computation preCompute(w, n); int[] queries = { 11, 10, 4 }; int q = queries.Length; // Perform queries for (int i = 0; i < q; i++) Console.WriteLine(ansQuery(queries[i])); }}// This code is contributed by sanjoy_62. |
Javascript
<script>// Javascript implementation of the approachvar C_MAX = 30var max_arr_len = 10// To store states of DPvar dp = Array.from(Array(max_arr_len), ()=>Array(C_MAX+1));// To check if a state has// been solvedvar v = Array.from(Array(max_arr_len), ()=>Array(C_MAX+1));// Function to compute the statesfunction findMax(i, r, w, n){ // Base case if (r < 0) return -1000000000; if (i == n) return 0; // Check if a state has // been solved if (v[i][r]) return dp[i][r]; // Setting a state as solved v[i][r] = 1; dp[i][r] = Math.max(w[i] + findMax(i + 1, r - w[i], w, n), findMax(i + 1, r, w, n)); // Returning the solved state return dp[i][r];}// Function to pre-compute the states// dp[0][0], dp[0][1], .., dp[0][C_MAX]function preCompute(w, n){ for (var i = C_MAX; i >= 0; i--) findMax(0, i, w, n);}// Function to answer a query in O(1)function ansQuery(w){ return dp[0][w];}// Driver codevar w = [3, 8, 9];var n = w.length;// Performing required// pre-computationpreCompute(w, n);var queries = [11, 10, 4];var q = queries.length;// Perform queriesfor (var i = 0; i < q; i++) document.write( ansQuery(queries[i])+ "<br>");</script> |
Output
11 9 3
Efficient approach: Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP to store the solution of the subproblems and initialize it with 0.
- Initialize the DP with base cases
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- After filling the DP now in Main function call every query and get the answer stored in DP.
Implementation :
C++
#include <bits/stdc++.h>#define C_MAX 30#define max_arr_len 10using namespace std;// Function to compute the maximum value that can be obtained// from the knapsack within the given capacityint dp[max_arr_len][C_MAX + 1] = {0};void findMax(int w[], int n, int c){ // Initializing the DP table with 0 // Filling the DP table bottom-up for (int i = 1; i <= n; i++) { for (int j = 1; j <= c; j++) { if (w[i - 1] <= j) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + w[i - 1]); } else { dp[i][j] = dp[i - 1][j]; } } } // Returning the maximum value that can be obtained return ;}// Driver codeint main(){ // Input array int w[] = { 3, 8, 9 }; int n = sizeof(w) / sizeof(int); // all given queries int queries[] = { 11, 10, 4 }; int q = sizeof(queries) / sizeof(queries[0]); // find maximum int ma = *max_element(queries, queries + q); // function call findMax(w, n , ma); // Perform queries for (int i = 0; i < q; i++) cout << dp[n][queries[i]] << endl; return 0;} |
Java
public class MaxSubsetSum { static int[][] findMax(int[] w, int n, int c) { // Initializing the DP table with 0 int[][] dp = new int[n + 1]; // Filling the DP table bottom-up for (int i = 1; i <= n; i++) { for (int j = 1; j <= c; j++) { if (w[i - 1] <= j) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + w[i - 1]); } else { dp[i][j] = dp[i - 1][j]; } } } return dp; } // Driver code public static void main(String[] args) { int[] w = {3, 8, 9}; int n = w.length; // All given queries int[] queries = {11, 10, 4}; int q = queries.length; // Find maximum int ma = Integer.MIN_VALUE; for (int query : queries) { ma = Math.max(ma, query); } // Function call int[][] dp = findMax(w, n, ma); // Perform queries for (int i = 0; i < q; i++) { System.out.println(dp[n][queries[i]]); } }} |
Python3
import sys# Function to compute the maximum value that can be obtained# from the knapsack within the given capacitydef findMax(w, n, c): # Initializing the DP table with 0 dp = [[0 for j in range(c + 1)] for i in range(n + 1)] # Filling the DP table bottom-up for i in range(1, n + 1): for j in range(1, c + 1): if w[i - 1] <= j: dp[i][j] = max(dp[i - 1][j], dp[i - 1] [j - w[i - 1]] + w[i - 1]) else: dp[i][j] = dp[i - 1][j] # Returning the maximum value that can be obtained return dp# Driver codeif __name__ == '__main__': # Input array w = [3, 8, 9] n = len(w) # all given queries queries = [11, 10, 4] q = len(queries) # find maximum ma = max(queries) # function call dp = findMax(w, n, ma) # Perform queries for i in range(q): print(dp[n][queries[i]]) |
C#
using System;public class MaxSubsetSum{ static int[,] findMax(int[] w, int n, int c) { // Initializing the DP table with 0 int[,] dp = new int[n + 1, c + 1]; // Filling the DP table bottom-up for (int i = 1; i <= n; i++) { for (int j = 1; j <= c; j++) { if (w[i - 1] <= j) { dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - w[i - 1]] + w[i - 1]); } else { dp[i, j] = dp[i - 1, j]; } } } return dp; } // Driver code public static void Main(string[] args) { int[] w = { 3, 8, 9 }; int n = w.Length; // All given queries int[] queries = { 11, 10, 4 }; int q = queries.Length; // Find maximum int ma = int.MinValue; foreach (int query in queries) { ma = Math.Max(ma, query); } // Function call int[,] dp = findMax(w, n, ma); // Perform queries for (int i = 0; i < q; i++) { Console.WriteLine(dp[n, queries[i]]); } }} |
Javascript
function findMax(w, n, c) { // Initializing the DP table with 0 let dp = new Array(n + 1).fill(null).map(() => new Array(c + 1).fill(0)); // Filling the DP table bottom-up for (let i = 1; i <= n; i++) { for (let j = 1; j <= c; j++) { if (w[i - 1] <= j) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + w[i - 1]); } else { dp[i][j] = dp[i - 1][j]; } } } // Returning the maximum value that can be obtained return dp;}// Driver codeconst w = [3, 8, 9];const n = w.length;// all given queriesconst queries = [11, 10, 4];const q = queries.length;// find maximumconst ma = Math.max(...queries);// function callconst dp = findMax(w, n, ma);// Perform queriesfor (let i = 0; i < q; i++) { console.log(dp[n][queries[i]]);} |
Output
11 9 3
Time complexity: O(n*c)
Auxiliary Space: O(n*C)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
