Given a knapsack with capacity C and two arrays w[] and val[] representing the weights and values of N distinct items, the task is to find the maximum value you can put into the knapsack. Items cannot be broken and an item with weight X takes X capacity of the knapsack.
Examples:
Input: w[] = {3, 4, 5}, val[] = {30, 50, 60}, C = 8
Output: 90
We take objects ‘1’ and ‘3’.
The total value we get is (30 + 60) = 90.
Total weight is 8, thus it fits in the given capacityInput: w[] = {10000}, val[] = {10}, C = 100000
Output: 10
Approach: The traditional famous 0-1 knapsack problem can be solved in O(N*C) time but if the capacity of the knapsack is huge then a 2D N*C array can’t make be made. Luckily, it can be solved by redefining the states of the dp.
Let’s have a look at the states of the DP first.
dp[V][i] represents the minimum weight subset of the subarray arr[i…N-1] required to get a value of at least V. The recurrence relation will be:
dp[V][i] = min(dp[V][i+1], w[i] + dp[V – val[i]][i + 1])
So, for each V from 0 to the maximum value of V possible, try to find if the given V can be represented with the given array. The largest such V that can be represented becomes the required answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define V_SUM_MAX 1000#define N_MAX 100#define W_MAX 10000000// To store the states of DPint dp[V_SUM_MAX + 1][N_MAX];bool v[V_SUM_MAX + 1][N_MAX];// Function to solve the recurrence relationint solveDp(int r, int i, vector<int>& w, vector<int>& val, int n){ // Base cases if (r <= 0) return 0; if (i == n) return W_MAX; if (v[r][i]) return dp[r][i]; // Marking state as solved v[r][i] = 1; // Recurrence relation dp[r][i] = min(solveDp(r, i + 1, w, val, n), w[i] + solveDp(r - val[i], i + 1, w, val, n)); return dp[r][i];}// Function to return the maximum weightint maxWeight(vector<int>& w, vector<int>& val, int n, int c){ // Iterating through all possible values // to find the largest value that can // be represented by the given weights for (int i = V_SUM_MAX; i >= 0; i--) { if (solveDp(i, 0, w, val, n) <= c) { return i; } } return 0;}// Driver codeint main(){ vector<int> w = { 3, 4, 5 }; vector<int> val = { 30, 50, 60 }; int n = (int)w.size(); int C = 8; cout << maxWeight(w, val, n, C); return 0;} |
Java
// Java implementation of the approachclass GFG { static final int V_SUM_MAX = 1000; static final int N_MAX = 100; static final int W_MAX = 10000000; // To store the states of DP static int dp[][] = new int[V_SUM_MAX + 1][N_MAX]; static boolean v[][] = new boolean [V_SUM_MAX + 1][N_MAX]; // Function to solve the recurrence relation static int solveDp(int r, int i, int w[], int val[], int n) { // Base cases if (r <= 0) return 0; if (i == n) return W_MAX; if (v[r][i]) return dp[r][i]; // Marking state as solved v[r][i] = true; // Recurrence relation dp[r][i] = Math.min(solveDp(r, i + 1, w, val, n), w[i] + solveDp(r - val[i], i + 1, w, val, n)); return dp[r][i]; } // Function to return the maximum weight static int maxWeight(int w[], int val[], int n, int c) { // Iterating through all possible values // to find the largest value that can // be represented by the given weights for (int i = V_SUM_MAX; i >= 0; i--) { if (solveDp(i, 0, w, val, n) <= c) { return i; } } return 0; } // Driver code public static void main (String[] args) { int w[] = { 3, 4, 5 }; int val[] = { 30, 50, 60 }; int n = w.length; int C = 8; System.out.println(maxWeight(w, val, n, C)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approachV_SUM_MAX = 1000N_MAX = 100W_MAX = 10000000# To store the states of DPdp = [[ 0 for i in range(N_MAX)] for i in range(V_SUM_MAX + 1)]v = [[ 0 for i in range(N_MAX)] for i in range(V_SUM_MAX + 1)]# Function to solve the recurrence relationdef solveDp(r, i, w, val, n): # Base cases if (r <= 0): return 0 if (i == n): return W_MAX if (v[r][i]): return dp[r][i] # Marking state as solved v[r][i] = 1 # Recurrence relation dp[r][i] = min(solveDp(r, i + 1, w, val, n), w[i] + solveDp(r - val[i], i + 1, w, val, n)) return dp[r][i]# Function to return the maximum weightdef maxWeight( w, val, n, c): # Iterating through all possible values # to find the largest value that can # be represented by the given weights for i in range(V_SUM_MAX, -1, -1): if (solveDp(i, 0, w, val, n) <= c): return i return 0# Driver codeif __name__ == '__main__': w = [3, 4, 5] val = [30, 50, 60] n = len(w) C = 8 print(maxWeight(w, val, n, C))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG { static readonly int V_SUM_MAX = 1000; static readonly int N_MAX = 100; static readonly int W_MAX = 10000000; // To store the states of DP static int [,]dp = new int[V_SUM_MAX + 1, N_MAX]; static bool [,]v = new bool [V_SUM_MAX + 1, N_MAX]; // Function to solve the recurrence relation static int solveDp(int r, int i, int []w, int []val, int n) { // Base cases if (r <= 0) return 0; if (i == n) return W_MAX; if (v[r, i]) return dp[r, i]; // Marking state as solved v[r, i] = true; // Recurrence relation dp[r, i] = Math.Min(solveDp(r, i + 1, w, val, n), w[i] + solveDp(r - val[i], i + 1, w, val, n)); return dp[r, i]; } // Function to return the maximum weight static int maxWeight(int []w, int []val, int n, int c) { // Iterating through all possible values // to find the largest value that can // be represented by the given weights for (int i = V_SUM_MAX; i >= 0; i--) { if (solveDp(i, 0, w, val, n) <= c) { return i; } } return 0; } // Driver code public static void Main(String[] args) { int []w = { 3, 4, 5 }; int []val = { 30, 50, 60 }; int n = w.Length; int C = 8; Console.WriteLine(maxWeight(w, val, n, C)); } }// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachvar V_SUM_MAX = 1000var N_MAX = 100var W_MAX = 10000000// To store the states of DPvar dp = Array.from(Array(V_SUM_MAX+1), ()=> Array(N_MAX));var v = Array.from(Array(V_SUM_MAX+1), ()=> Array(N_MAX));// Function to solve the recurrence relationfunction solveDp(r, i, w, val, n){ // Base cases if (r <= 0) return 0; if (i == n) return W_MAX; if (v[r][i]) return dp[r][i]; // Marking state as solved v[r][i] = 1; // Recurrence relation dp[r][i] = Math.min(solveDp(r, i + 1, w, val, n), w[i] + solveDp(r - val[i], i + 1, w, val, n)); return dp[r][i];}// Function to return the maximum weightfunction maxWeight(w, val, n, c){ // Iterating through all possible values // to find the largest value that can // be represented by the given weights for (var i = V_SUM_MAX; i >= 0; i--) { if (solveDp(i, 0, w, val, n) <= c) { return i; } } return 0;}// Driver codevar w = [3, 4, 5];var val = [30, 50, 60];var n = w.length;var C = 8;document.write( maxWeight(w, val, n, C));</script> |
Output:
90
Time Complexity: O(V_sum * N) where V_sum is the sum of all the values in the array val[].
Auxiliary Space : O(V_sum * N) where V_sum is the sum of all the values in the array val[].
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 table DP to store the solution of the subproblems.
- Initialize the table with base cases
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- At last get the maximum value from DP and return the final solution.
Implementation :
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;#define V_SUM_MAX 1000#define N_MAX 100#define W_MAX 10000000// Function to return the maximum weightint maxWeight(vector<int>& w, vector<int>& val, int n, int c){ // Initialize dp array int dp[V_SUM_MAX + 1][N_MAX + 1]; for (int i = 0; i <= V_SUM_MAX; i++) for (int j = 0; j <= n; j++) dp[i][j] = W_MAX; // Base case initialization for (int i = 0; i <= n; i++) dp[0][i] = 0; // iterate over subproblems ans get // the current value from previous computation for (int i = 1; i <= V_SUM_MAX; i++) for (int j = 1; j <= n; j++) dp[i][j] = min( dp[i][j - 1], (i >= val[j - 1]) ? w[j - 1] + dp[i - val[j - 1]][j - 1] : W_MAX); // Finding maximum value for (int i = V_SUM_MAX; i >= 0; i--) if (dp[i][n] <= c) return i; return 0;}// Driver codeint main(){ vector<int> w = { 3, 4, 5 }; vector<int> val = { 30, 50, 60 }; int n = (int)w.size(); int C = 8; cout << maxWeight(w, val, n, C); return 0;} |
Python3
import sysV_SUM_MAX = 1000N_MAX = 100W_MAX = 10000000# Function to return the maximum weightdef maxWeight(w, val, n, c): # Initialize dp array dp = [[W_MAX for j in range(n+1)] for i in range(V_SUM_MAX+1)] # Base case initialization for i in range(n+1): dp[0][i] = 0 # iterate over subproblems ans get # the current value from previous computation for i in range(1, V_SUM_MAX+1): for j in range(1, n+1): dp[i][j] = min(dp[i][j-1], w[j-1]+dp[i-val[j-1]] [j-1] if i >= val[j-1] else W_MAX) # Finding maximum value for i in range(V_SUM_MAX, -1, -1): if dp[i][n] <= c: return i return 0# Driver codeif __name__ == "__main__": w = [3, 4, 5] val = [30, 50, 60] n = len(w) C = 8 print(maxWeight(w, val, n, C)) |
Java
import java.util.*;class Main { public static final int V_SUM_MAX = 1000; public static final int N_MAX = 100; public static final int W_MAX = 10000000; // Function to return the maximum weight public static int maxWeight(List<Integer> w, List<Integer> val, int n, int c) { // Initialize dp array int[][] dp = new int[V_SUM_MAX + 1][N_MAX + 1]; for (int i = 0; i <= V_SUM_MAX; i++) { for (int j = 0; j <= n; j++) { dp[i][j] = W_MAX; } } // Base case initialization for (int i = 0; i <= n; i++) { dp[0][i] = 0; } // iterate over subproblems ans get // the current value from previous computation for (int i = 1; i <= V_SUM_MAX; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = Math.min( dp[i][j - 1], (i >= val.get(j - 1)) ? w.get(j - 1) + dp[i - val.get(j - 1)] [j - 1] : W_MAX); } } // Finding maximum value for (int i = V_SUM_MAX; i >= 0; i--) { if (dp[i][n] <= c) { return i; } } return 0; } // Driver code public static void main(String[] args) { List<Integer> w = new ArrayList<>(Arrays.asList(3, 4, 5)); List<Integer> val = new ArrayList<>(Arrays.asList(30, 50, 60)); int n = w.size(); int C = 8; System.out.println(maxWeight(w, val, n, C)); }} |
C#
using System;public class KnapsackMaxWeight{ private const int V_SUM_MAX = 1000; private const int N_MAX = 100; private const int W_MAX = 10000000; public static int MaxWeight(int[] w, int[] val, int n, int c) { // Initialize dp array int[,] dp = new int[V_SUM_MAX + 1, N_MAX + 1]; for (int i = 0; i <= V_SUM_MAX; i++) { for (int j = 0; j <= n; j++) { dp[i, j] = W_MAX; } } // Base case initialization for (int i = 0; i <= n; i++) { dp[0, i] = 0; } // iterate over subproblems ans get // the current value from previous computation for (int i = 1; i <= V_SUM_MAX; i++) { for (int j = 1; j <= n; j++) { dp[i, j] = Math.Min( dp[i, j - 1], (i >= val[j - 1]) ? w[j - 1] + dp[i - val[j - 1], j - 1] : W_MAX); } } // Finding maximum value for (int i = V_SUM_MAX; i >= 0; i--) { if (dp[i, n] <= c) { return i; } } return 0; } public static void Main() { int[] w = { 3, 4, 5 }; int[] val = { 30, 50, 60 }; int n = w.Length; int c = 8; Console.WriteLine(MaxWeight(w, val, n, c)); }} |
Javascript
function MaxWeight(w, val, n, c) { // Initialize dp array const V_SUM_MAX = 1000; const N_MAX = 100; const W_MAX = 10000000; const dp = new Array(V_SUM_MAX + 1).fill().map(() => new Array(N_MAX + 1).fill(W_MAX)); // Base case initialization for (let i = 0; i <= n; i++) { dp[0][i] = 0; } // iterate over subproblems and get // the current value from previous computation for (let i = 1; i <= V_SUM_MAX; i++) { for (let j = 1; j <= n; j++) { dp[i][j] = Math.min( dp[i][j - 1], (i >= val[j - 1]) ? w[j - 1] + dp[i - val[j - 1]][j - 1] : W_MAX ); } } // Finding maximum value for (let i = V_SUM_MAX; i >= 0; i--) { if (dp[i][n] <= c) { return i; } } return 0;}const w = [3, 4, 5];const val = [30, 50, 60];const n = w.length;const c = 8;console.log(MaxWeight(w, val, n, c)); |
Output
90
Time Complexity: O(V_sum * N).
Auxiliary Space : O(V_sum * N).
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!
