DEV Community: Pradeepsingh Bhati

The fractional knapsack problem

Pradeepsingh Bhati — Fri, 19 Mar 2021 18:14:07 +0000

The fractional knapsack problem is a greedy-based problem and also an extension of the classic 0-1 knapsack problem. You can read about the 0-1 knapsack problem here.

Problem Description

Given n items having certain value and weight, put these items in a knapsack with given maximum capacity (maxWeight). The goal here is to find possible maximum total value in the knapsack. Here fraction of items can be used i.e we can break an item. For example :

Input:
n=3
maxWeight=50
weights={10,20,30}
value={50,40,90}

Output:
160.00

In the above example, we can fully select item 0 and item 2. This will give total value = 50+90 = 140 with total weight = 10+30 = 40. For remaining weight space of 50-40=10, we can use (1/2)th of item 1 which will have weight = 20/2 = 10 and value 40/2=20. So total value will be 50+90+20 = 160 and total weight will be 10+30+10=50 i.e. <=maxWeight. This is the possible maximum answer.

Observation

Here the key observation is that we need to use items fully until we lack weight space for the particular item. In that scenario, we can break the item to fill the left weight space.

Greedy approach

As we can break the item into any fraction and use it, we need to normalize it. Suppose we have an item of weight = a and value = b, we can break that item into 'a' number of items each of value (b/a). For eg. if we have an item of weight = 30 and value = 120, we can break that item into 30 items, each having value (120/30)=4 i.e. we have 30 items having weight = 1 and value = 4.

To maximize the total value inside the knapsack, we will sort the items with reference to (value/weight) ratio using the custom compare function in Sort(). One by one we will check for an item and as per the left weight space out of maxWeight inside the knapsack, we will use the current weight.

Case 1: If our current item is having a weight less than or equal to the left weight space inside the knapsack, we didn't need to break the item as the whole item can be accommodated inside, so we will add that item fully. If we have an item of weight 10 and the left weight space in the knapsack is 20 then we can use that item fully without breaking it.

Case 2: If our current item is having a weight more than the left weight space inside the knapsack, we will break the item and use only the fraction that is required. For eg., if we have the capacity(max weight) of knapsack = 10 and the current total weight of knapsack = 8. Current item is having weight = 30 and value = 120. In order to fill 10-8 = 2 weight space in knapsack we will use only (1/15)th of item i.e weight = (30/15) = 2 having value (120/30)*2 = 8.

struct Item{
    int weight,value;

};

class greedy_approach{

    static bool compare(Item a,Item b){
        return (double)a.value/a.weight>(double)b.value/b.weight;
    }

    public:
    double fractional_knapsack(int maxWeight,int n,Item weights[]){
        sort(weights,weights+n,compare);
        double ans = 0 ;
        for(int i=0;i<n;i++){
            if(maxWeight>=weights[i].weight){
                maxWeight-=weights[i].weight;
                ans+=weights[i].value;
            }else{
                ans+=maxWeight*(double)weights[i].value/weights[i].weight;
                break;
            }
        }
        return ans;
    }
};

Here we use Item struct to reduce code complexity and can avoid making extra vectors and maps to store weights and values.

Time Complexity : O(n*logn). We use Sort() and an O(n) loop. The sort takes approx. n*logn time.
Space Complexity : O(n).

Unbounded Knapsack Problem

Pradeepsingh Bhati — Fri, 05 Mar 2021 16:34:11 +0000

The unbounded knapsack problem is a dynamic programming-based problem and also an extension of the classic 0-1 knapsack problem. You can read about 0-1 knapsack problem here.

Problem Description

Given n weights having a certain value put these weights in a knapsack with a given capacity (maxWeight). The total weight of the knapsack after adding weights must remain smaller than or equal to capacity(maxWeight). The goal here is to find possible maximum total value in the knapsack. Any weight can be selected multiple times i.e. repetitions are allowed. For example :

Input:
n=2
maxWeight=3
weights={2,1}
value={1,1}

Output:
3

In the above example, we can select weights {1} for 3 times giving knapsack total weight as 3 and total value as 3 which is the maximum possible value.

Observation

Here the key observation is that we need to find the subset of weights whose weight sum is less than or equal to the capacity of the knapsack and having maximum value sum. Here any weight can be added multiple times in the subset.

Recursive Approach

Recursively we will move from index 0 to n-1 and will perform two operations:

Add the current weight. We will only select the current weight if the total weight inside the knapsack after selecting remains under the given capacity else will ignore it. If selected, we will call for the same index again because we can select a weight more than once.
Don't add the current weight. Here we will move to the next index (i.e i+1)

We will return the maximum of both operations as we have to maximize the total value. Here we will stop at index==n because there's no weight to add in the knapsack. You can see in the code that it is selecting the weight and calling the same index again to check if the same weight can be added again. Also, we are considering the possibility of not selecting the weight. So in the end, the maximum answer for a particular weight after considering both possibilities is returned. At last, we have final answer.

        int rec_helper(int curWeightSum,int i,int n,int wt[],int val[],int maxWeight,int **dp){
            if(i==n){
                return 0;
            }
            if(dp[i][curWeightSum]!=-1){
                return dp[i][curWeightSum];
            }
            dp[i][curWeightSum] = rec_helper(curWeightSum,i+1,n,wt,val,maxWeight,dp);
            if(curWeightSum+wt[i]<=maxWeight) {
                dp[i][curWeightSum] = max(dp[i][curWeightSum],
                                          val[i] + rec_helper(curWeightSum + wt[i], i, n, wt, val, maxWeight, dp));
            }
            return dp[i][curWeightSum];
        }
        int unbounded_knapsack(int n,int wt[],int val[],int maxWeight){
            int** dp=new int*[n];
            for(int i=0;i<n;i++){
                dp[i]=new int[maxWeight+1];
                for(int j=0;j<maxWeight+1;j++){
                    dp[i][j]=-1;
                }
            }
            return rec_helper(0,0,n,wt,val,maxWeight,dp);
        }

Memoization - Here I used a 2d array - 'dp' to store the recursion calls so that we can use the stored value in dp for repeated recursion calls instead. This is useful for reducing time complexity.

Time Complexity : O(n*maxWeight*maxWeight). For every weight we are going till maxWeight. And every weight is selected for multiple times reaching maxweight.
Space Complexity : O(n*maxWeight). We used 2-d array dp as extra space

Dynamic Approach

Tabulation is done using a one-dimensional array(dp) in this case. Whose dimension is the same as maxWeight+1. Here we do the same two operations stated in the recursive approach:

If we have to form a knapsack of capacity j and we have current weight under consideration as weights[i], which is <=j, with value[i]. If we add the current weights[i] in the knapsack, we need to find the maximum value for the knapsack of total weight (j-weight[i]) from the dp which contains solutions till current weight(included), and then add value[i] of weights[i] weight in that. In case we don't have a knapsack of total weight (j-weights[i]) then 0 will be added and the value[i] of current weights[i] will become the total of values for that particular knapsack. If we have the current weight as 3 and required j=5 then we need to find a knapsack of weight 5-3=2. Here the important difference from 0-1 knapsack problem is that we are iterating the dp from 0 to maxWeight(included). This is because we also need solutions for current weight till the current required knapsack weight(j) as weights can be used for multiple times.
If we don't select the weight, the value of that cell remains unchanged as it already describes the answer till now for particular j.

         int unbounded_knapsack(int n,int wt[],int val[],int maxWeight){
            int dp[maxWeight+1];
            for(int i=0;i<maxWeight+1;i++){
                dp[i]=0;
            }
            for(int i=0;i<n;i++){
                for(int j=wt[i];j<maxWeight+1;j++){
                    dp[j]=max(dp[j],val[i]+dp[j-wt[i]]);
                }
            }
            return dp[maxWeight];
        }

Here the cell value in the dp array will be the maximum of operation1 and operation2. I used 1-d array, where jth cell represents a knapsack with weight j while performing operations on a particular ith weight. Hence the array will hold results till (i-1)th weight while running for ith weight. Returning dp[maxWeight] will give the answer. Initially, all the values of the array is 0 as it will be the maximum for an empty knapsack.

Time Complexity : O(n*maxWeight).
Space Complexity : O(maxWeight). We used 2-d array dp as extra space

Unbounded Knapsack Problem - DP

Pradeepsingh Bhati — Wed, 03 Mar 2021 20:46:48 +0000

The unbounded knapsack problem is a dynamic programming-based problem and also an extension of the classic 0-1 knapsack problem. You can read about 0-1 knapsack problem here.

Problem Description

Input:
n=2
maxWeight=3
weights={2,1}
value={1,1}

Output:
3

In the above example, we can select weights {1} for 3 times giving knapsack total weight as 3 and total value as 3 which is the maximum possible value.

Observation

Recursive Approach

Recursively we will move from index 0 to n-1 and will perform two operations:

Add the current weight. We will only select the current weight if the total weight inside the knapsack after selecting remains under the given capacity else will ignore it. If selected, we will call for the same index again because we can select a weight more than once.
Don't add the current weight. Here we will move to the next index (i.e i+1)

        int rec_helper(int curWeightSum,int i,int n,int wt[],int val[],int maxWeight,int **dp){
            if(i==n){
                return 0;
            }
            if(dp[i][curWeightSum]!=-1){
                return dp[i][curWeightSum];
            }
            dp[i][curWeightSum] = rec_helper(curWeightSum,i+1,n,wt,val,maxWeight,dp);
            if(curWeightSum+wt[i]<=maxWeight) {
                dp[i][curWeightSum] = max(dp[i][curWeightSum],
                                          val[i] + rec_helper(curWeightSum + wt[i], i, n, wt, val, maxWeight, dp));
            }
            return dp[i][curWeightSum];
        }
        int unbounded_knapsack(int n,int wt[],int val[],int maxWeight){
            int** dp=new int*[n];
            for(int i=0;i<n;i++){
                dp[i]=new int[maxWeight+1];
                for(int j=0;j<maxWeight+1;j++){
                    dp[i][j]=-1;
                }
            }
            return rec_helper(0,0,n,wt,val,maxWeight,dp);
        }

Memoization - Here I used a 2d array - 'dp' to store the recursion calls so that we can use the stored value in dp for repeated recursion calls instead. This is useful for reducing time complexity.

Dynamic Approach

Tabulation is done using a one-dimensional array(dp) in this case. Whose dimension is the same as maxWeight+1. Here we do the same two operations stated in the recursive approach:

If we have to form a knapsack of capacity j and we have current weight under consideration as weights[i], which is <=j, with value[i]. If we add the current weights[i] in the knapsack, we need to find the maximum value for the knapsack of total weight (j-weight[i]) from the dp which contains solutions till current weight(included), and then add value[i] of weights[i] weight in that. In case we don't have a knapsack of total weight (j-weights[i]) then 0 will be added and the value[i] of current weights[i] will become the total of values for that particular knapsack. If we have the current weight as 3 and required j=5 then we need to find a knapsack of weight 5-3=2. Here the important difference from 0-1 knapsack problem is that we are iterating the dp from 0 to maxWeight(included). This is because we also need solutions for current weight till the current required knapsack weight(j) as weights can be used for multiple times.
If we don't select the weight, the value of that cell remains unchanged as it already describes the answer till now for particular j.

         int unbounded_knapsack(int n,int wt[],int val[],int maxWeight){
            int dp[maxWeight+1];
            for(int i=0;i<maxWeight+1;i++){
                dp[i]=0;
            }
            for(int i=0;i<n;i++){
                for(int j=wt[i];j<maxWeight+1;j++){
                    dp[j]=max(dp[j],val[i]+dp[j-wt[i]]);
                }
            }
            return dp[maxWeight];
        }

Time Complexity : O(n*maxWeight).
Space Complexity : O(maxWeight). We used 2-d array dp as extra space

0-1 Knapsack Problem

Pradeepsingh Bhati — Tue, 23 Feb 2021 14:37:44 +0000

0-1 Knapsack problem is one of the most important problems based on the concept of Dynamic programming. Dynamic Programming(DP) is an algorithmic concept for solving optimization problems. In simple words, we try to break problems into subproblems and find their optimal solution which leads to the optimal overall solution. Let's understand the problem statement first.

Problem Description

Input:
n=4
maxWeight=5
weights={4,3,5,1}
value={1,2,2,3}

Output:
5

In the above example, weights:{3,1} with value:{2,3} respectively will have a total value of 5 which is the maximum among any combination of weights.

Observation

Here the key observation is that we need to find the subset of weights whose weight sum is less than or equal to the capacity of the knapsack and having maximum value sum.

Recursive Approach

Recursively we will move from index 0 to n-1 and will perform two operations:

Add the current weight (Add element to a subset). We will only select the current weight if the total weight inside the knapsack after selecting remains under the given capacity else will ignore it.
Don't Add the current weight (Don't add an element to a subset).

We will recursively call the next element after performing may be any one or both operations given above as per the conditions. We will return the maximum of both operations as we have to find the maximum total value. We have to stop and return when we reach beyond the array size. So in the end, we will have a maximum of all such subsets where we made choices to select the weight with a certain value or ignore it.

        int rec_helper(int curWeightSum,int i,int n,int wt[],int val[],int maxWeight,int **dp){
            if(i==n){
                return 0;
            }
            if(dp[i][curWeightSum]!=-1){
                return dp[i][curWeightSum];
            }

            dp[i][curWeightSum] = rec_helper(curWeightSum,i+1,n,wt,val,maxWeight,dp);

            if(curWeightSum+wt[i]<=maxWeight) {
                dp[i][curWeightSum] = max(dp[i][curWeightSum],
                                          val[i] + rec_helper(curWeightSum + wt[i], i + 1, n, wt, val, maxWeight, dp));
            }

            return dp[i][curWeightSum];
        }

        int knapsack(int n,int wt[],int val[],int maxWeight){
            int** dp=new int*[n];
            for(int i=0;i<n;i++){
                dp[i]=new int[maxWeight+1];

                for(int j=0;j<maxWeight+1;j++){
                    dp[i][j]=-1;
                }
            }
            return rec_helper(0,0,n,wt,val,maxWeight,dp);
        }

Memoization - Here I used a 2d array - 'dp' to store the recursion calls so that we can use the stored value in dp for repeated recursion calls instead. This is useful for reducing time complexity.

Time Complexity : O(n*maxWeight). As we avoided most repeating calls.
Space Complexity : O(n*maxWeight). We used 2-d array dp as extra space

Dynamic Approach

Tabulation is done using a one-dimensional array in this case. Whose dimension is the same as maxWeight+1(capacity of knapsack). Here we do the same two operations stated in the recursive approach:

If we have to form a knapsack of capacity j and we have current weight under consideration as weights[i], which is <=j, with value[i]. If we add the current weights[i] in the knapsack, we need to find the maximum value for the knapsack of total weight (j-weight[i]) till previous iterations and then add value[i] of weights[i] weight in that. In case we don't have a knapsack of total weight (j-weights[i]) then 0 will be added and the value[i] of current weights[i] will become the total of values for that particular knapsack. If we have the current weight as 3 and required j=5 then we need to find a knapsack of weight 5-3=2.
If we don't select the weight, the value of that cell in dp array will be the answer to the previous iteration for that particular j.

int dp[maxWeight+1];
for(int i=0;i<maxWeight+1;i++){
   dp[i]=0;
}
for(int i=0;i<n;i++){
   for(int j=maxWeight;j>=wt[i];j--){
       dp[j]=max(dp[j],val[i]+dp[j-wt[i]]);
   }
}
return dp[maxWeight];

Time Complexity : O(n*maxWeight).
Space Complexity : O(maxWeight). We used 2-d array dp as extra space