Maximum items that can be filled in K Knapsacks of given Capacity

0 0 8 minutes read

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 = 11

Input : 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 DP
vector<vector<int> > dp;
 
// 2-d array to store if a state
// has been solved
vector<vector<bool> > v;
 
// Vector to store power of variable 'C'.
vector<int> exp_c;
 
// function to compute the states
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] = 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 Code
int 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 DP
x = 100
dp = [[0 for i in range(x)] 
         for i in range(x)]
 
# 2-d array to store if a state
# has been solved
v = [[0 for i in range(x)]  
        for i in range(x)]
 
# Vector to store power of variable 'C'.
exp_c = []
 
# function to compute the states
def 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 array
w =[3, 8, 9]
 
# number of knapsacks and capacity
k = 1
c = 11
 
n = len(w)
 
# Performing required pre-computation
r = PreCompute(n, c, k)
 
# finding the required answer
print(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 DP
static 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 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[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:

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 zambiatek!