Given an integer array W[] consisting of weights of items and ‘K’ knapsacks of capacity ‘C’, find maximum weight we can put in the knapsacks if breaking of an item is not allowed.
Examples:
Input : w[] = {3, 9, 8}, k = 1, c = 11
Output : 11
The required subset will be {3, 8}
where 3+8 = 11Input : w[] = {3, 9, 8}, k = 1, c = 10
Output : 9
We will use Dynamic programming to solve this problem.
We will use two variables to represent the states of DP.
- ‘i’ – The current index we are working on.
- ‘R’ – It contains the remaining capacity of each and every knapsack.
Now, how will a single variable store the remaining capacity of every knapsack?
For that, we will initialise ‘R’ as R = C + C*(C+1) + C*(C+1)^2 + C*(C+1)^3 ..+ C*(C+1)^(k-1)
This initialises all the ‘k’ knapsacks with capacity ‘C’.
Now, we need to perform two queries:
- Reading remaining space of jth knapsack: (r/(c+1)^(j-1))%(c+1).
- Decreasing remaining space of jth knapsack by x: set r = r – x*(c+1)^(j-1).
Now, at each step, we will have k+1 choices.
- Reject index ‘i’.
- Put item ‘i’ in knapsack 1.
- Put item ‘i’ in knapsack 2.
- Put item ‘i’ in knapsack 3.
We will choose the path that maximizes the result.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>using namespace std;// 2-d array to store states of DPvector<vector<int> > dp;// 2-d array to store if a state// has been solvedvector<vector<bool> > v;// Vector to store power of variable 'C'.vector<int> exp_c;// function to compute the statesint FindMax(int i, int r, int w[], int n, int c, int k){ // Base case if (i >= n) return 0; // Checking 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] = FindMax(i + 1, r, w, n, c, k); // Recurrence relation 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)); } // Returning the solved state return dp[i][r];}// Function to initialize global variables// and find the initial value of 'R'int PreCompute(int n, int c, int k){ // Resizing the variables 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); } // Variable to store the initial value of R int R = 0; for (int i = 0; i < k; i++){ R += exp_c[i] * c; } return R;}// Driver Codeint main(){ // Input array int w[] = { 3, 8, 9 }; // number of knapsacks and capacity int k = 1, c = 11; int n = sizeof(w) / sizeof(int); // Performing required pre-computation int r = PreCompute(n, c, k); // finding the required answer cout << FindMax(0, r, w, n, c, k); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { // 2-d array to store if a state // has been solved static ArrayList<ArrayList<Boolean>> v = new ArrayList<ArrayList<Boolean>>(); // 2-d array to store states of DP static ArrayList<ArrayList<Integer>> dp = new ArrayList<ArrayList<Integer>>(); // Vector to store power of variable 'C'. static ArrayList<Integer> exp_c = new ArrayList<Integer>(); // function to compute the states static int FindMax(int i, int r, int w[], int n, int c, int k) { // Base case if (i >= n) { return 0; } // Checking if a state has been solved if(v.get(i).get(r)) { return dp.get(i).get(r); } // Setting a state as solved v.get(i).set(r, true); dp.get(i).set(r,FindMax(i + 1, r, w, n, c, k)); // Recurrence relation for (int j = 0; j < k; j++) { int x = (r / exp_c.get(j)) % (c + 1); if (x - w[i] >= 0) { dp.get(i).set(r,Math.max(dp.get(i).get(r),w[i] + FindMax(i + 1, r - w[i] * exp_c.get(j), w, n, c, k))); } } // Returning the solved state return dp.get(i).get(r); } // Function to initialize global variables // and find the initial value of 'R' static int PreCompute(int n, int c, int k) { // Resizing the variables for(int i = 0; i < k; i++) { exp_c.add(0); } exp_c.set(0, 1); for (int i = 1; i < k; i++) { exp_c.set(i,(exp_c.get(i - 1) * (c + 1))); } for (int i = 0; i < n; i++) { dp.add(new ArrayList<Integer>()); } for (int i = 0; i < n; i++) { for(int j = 0; j < (exp_c.get(k-1) * (c + 1)) ; j++ ) { dp.get(i).add(0); } } for (int i = 0; i < n; i++) { v.add(new ArrayList<Boolean>(Arrays.asList( new Boolean[(exp_c.get(k-1) * (c + 1))]))); } for (int i = 0; i < n; i++) { Collections.fill(v.get(i), Boolean.FALSE); } // Variable to store the initial value of R int R = 0; for(int i = 0; i < k; i++) { R += exp_c.get(i) * c; } return R; } // Driver Code public static void main (String[] args) { // Input array int w[] = { 3, 8, 9 }; // number of knapsacks and capacity int k = 1, c = 11; int n = w.length; // Performing required pre-computation int r = PreCompute(n, c, k); // finding the required answer System.out.println(FindMax(0, r, w, n, c, k)); }}// This code is contributed by avanitrachhadiya2155 |
Python3
# 2-d array to store states of DPx = 100dp = [[0 for i in range(x)] for i in range(x)]# 2-d array to store if a state# has been solvedv = [[0 for i in range(x)] for i in range(x)]# Vector to store power of variable 'C'.exp_c = []# function to compute the statesdef FindMax(i, r, w, n, c, k): # Base case if (i >= n): return 0 # Checking 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] = FindMax(i + 1, r, w, n, c, k) # Recurrence relation for j in range(k): 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)) # Returning the solved state return dp[i][r]# Function to initialize global variables# and find the initial value of 'R'def PreCompute(n, c, k): # Resizing the variables exp_c.append(1) for i in range(1, k): exp_c[i] = (exp_c[i - 1] * (c + 1)) # Variable to store the initial value of R R = 0 for i in range(k): R += exp_c[i] * c return R# Driver Code# Input arrayw =[3, 8, 9]# number of knapsacks and capacityk = 1c = 11n = len(w)# Performing required pre-computationr = PreCompute(n, c, k)# finding the required answerprint(FindMax(0, r, w, n, c, k))# This code is contributed by Mohit Kumar |
C#
using System;using System.Collections.Generic;class GFG{// 2-d array to store if a state // has been solved static List<List<bool>> v = new List<List<bool>>();// 2-d array to store states of DPstatic List<List<int>> dp = new List<List<int>>();// Vector to store power of variable 'C'.static List<int> exp_c = new List<int>();// Function to compute the statesstatic int FindMax(int i, int r, int[] w, int n, int c, int k) { // Base case if (i >= n) { return 0; } // Checking 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] = FindMax(i + 1, r, w, n, c, k); // Recurrence relation for(int j = 0; j < k; j++) { int x = (r / exp_c[j]) % (c + 1); if (x - w[i] >= 0) { dp[i][r] = Math.Max(dp[i][r], w[i] + FindMax(i + 1, r - w[i] * exp_c[j], w, n, c, k)); } } // Returning the solved state return dp[i][r];}// Function to initialize global variables // and find the initial value of 'R'static int PreCompute(int n, int c, int k){ // Resizing the variables for(int i = 0; i < k; i++) { exp_c.Add(0); } exp_c[0] = 1; for(int i = 1; i < k; i++) { exp_c[i] = (exp_c[i - 1] * (c + 1)); } for(int i = 0; i < n; i++) { dp.Add(new List<int>()); } for(int i = 0; i < n; i++) { for(int j = 0; j < (exp_c[k - 1] * (c + 1)); j++ ) { dp[i].Add(0); } } for(int i = 0; i < n; i++) { v.Add(new List<bool>()); } for(int i = 0; i < n; i++) { for(int j = 0; j < (exp_c[k - 1] * (c + 1)); j++ ) { v[i].Add(false); } } // Variable to store the initial value of R int R = 0; for(int i = 0; i < k; i++) { R += exp_c[i] * c; } return R;}// Driver code static public void Main(){ // Input array int[] w = { 3, 8, 9 }; // number of knapsacks and capacity int k = 1, c = 11; int n = w.Length; // Performing required pre-computation int r = PreCompute(n, c, k); // finding the required answer Console.WriteLine(FindMax(0, r, w, n, c, k));}}// This code is contributed by rag2127 |
Javascript
<script> // 2-d array to store if a state // has been solved let v =[]; // 2-d array to store states of DP let dp =[]; // Vector to store power of variable 'C'. let exp_c =[]; // function to compute the states function FindMax(i,r,w,n,c,k) { // Base case if (i >= n) { return 0; } // Checking 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] =FindMax(i + 1, r, w, n, c, k); // Recurrence relation for (let j = 0; j < k; j++) { let x = (r / exp_c[j]) % (c + 1); if (x - w[i] >= 0) { dp[i][r] = Math.max(dp[i][r],w[i] + FindMax(i + 1, r - w[i] * exp_c[j], w, n, c, k)); } } // Returning the solved state return dp[i][r]; } // Function to initialize global variables // and find the initial value of 'R' function PreCompute(n,c,k) { // Resizing the variables for(let i = 0; i < k; i++) { exp_c.push(0); } exp_c[0]= 1; for (let i = 1; i < k; i++) { exp_c[i]=(exp_c[i - 1] * (c + 1)); } for (let i = 0; i < n; i++) { dp.push([]); } for (let i = 0; i < n; i++) { for(let j = 0; j < (exp_c[k-1] * (c + 1)) ; j++ ) { dp[i][0]; } } for (let i = 0; i < n; i++) { v.push([(exp_c[k-1] * (c + 1))]); } for (let i = 0; i < n; i++) { for(let j=0;j<v[i].length;j++) { v[i][j]=false; } } // Variable to store the initial value of R let R = 0; for(let i = 0; i < k; i++) { R += exp_c[i] * c; } return R; } // Driver Code // Input array let w=[3, 8, 9]; // number of knapsacks and capacity let k = 1, c = 11; let n = w.length; // Performing required pre-computation let r = PreCompute(n, c, k); // finding the required answer document.write(FindMax(0, r, w, n, c, k));// This code is contributed by unknown2108</script> |
Output:
11
Time complexity : O(N*k*C^k).
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!
