Unbounded fractional knapsack problem in Java

By Adit Gupta

In this tutorial, I will show how to solve the problem of unbounded fractional knapsack problem in Java language. It is somewhat different from the conventional knapsack problem. There can be repetition of items with highest priority in this knapsack problem. We will see this further with the help of an example. So let us get started.

Unbounded Fractional Knapsack with repetition of items

As stated earlier, this algorithm is slightly different from the conventional knapsack problem. In the conventional knapsack problem, we are not allowed the repetition of items. Consequently, one item can be used only once. If there are space limitations, then a part of some item (in fractional knapsack). However, in unbounded fractional knapsack, you can choose the same item again and again. There can be repetition of items with highest priority. Moreover, since it is a fractional case, we can at last go for fraction of the most prioritized item when there are space limitations.

Let us try to understand this with the help of an example:

value[]   = [140, 225, 80, 240, 120]

weight[] =[10,  15, 10, 20, 12]

Capacity = 50kg

Output: 750

Approach for repetition of items

I will be using the OOPS concept of Java to implement this approach. I have a void output() function that takes 3 parameters. In this function, I will first of all obtain the value to weight ratio for each item. I then sorted this ratio in descending order so as to give priority to the item with highest ratio.

After that I have calculated how many times, the item with highest ratio, can be chosen completely. I put the value and weight those many times just by simply multiplying and storing in separate variables. Now we will check the space left in our bag. We will find out what part is it of the whole item and just multiply this ratio by its corresponding value. As a result, we will get the value for this part by unitary method.

In the main function, we will carry out our input and object creation. First, we need to make instance of our Scanner class so as to be able to take input. Once our initialization is done, I will make object of our class and call our output() function.

The code is shown below:

import java.util.*;
public class unbounded_knapsack 
{
    public void output(int value[], int weight[], int W)
    {
        int i;
        int t = value.length;
        System.out.println("Length: " + t);
        double ratio[] = new double[t];
        double max = 0.0;

        //obtain value to weight ratio
        for(i=0;i<t;i++)
        {
            ratio[i] = value[i]/(double)weight[i];
        }

        //sort in descending order
        for(i=0;i<t;++i)
        {
            for(int j=i+1;j<t;++j)
            {
                if(ratio[i]<ratio[j])
                {
                    double swap1 = ratio[i];
                    ratio[i] = ratio[j];
                    ratio[j] = swap1;

                    int swap2 = value[i];
                    value[i] = value[j];
                    value[j] = swap2;

                    int swap3 = weight[i];
                    weight[i] = weight[j];
                    weight[j] = swap3;

                }
            }   
        }

        double output_val = 0.0;
        //check how many complete units can be taken
        int x = W/weight[0];
        int temp_W = 0;
        //get value for completem units of item
        temp_W = temp_W + x*weight[0];
        output_val = output_val + x*value[0];
        int space = W - temp_W;
        //add the remaining value corresponding to the fraction left
        output_val = output_val + (space/(double)weight[0])*value[0];

        System.out.println(output_val);
        System.out.println(x + " complete units of item 1 plus " + space + "/" + weight[0] + " units of item 1");        
    }
    
    public static void main(String[] args)
    {
        Scanner ob = new Scanner(System.in);
        System.out.print("Enter number of items: ");
        int n = ob.nextInt();
        System.out.println(" ");
        int v[] = new int[n];
        int w[] = new int[n];
        System.out.print("Enter target: ");
        System.out.println(" ");
        int W=ob.nextInt();
        for(int i=0;i<n;i++)
        {
            System.out.println("Enter value  " + (i+1) + ": ");
            v[i] = ob.nextInt();
            System.out.println("Enter weight " + (i+1) + ": ");
            w[i] = ob.nextInt();
        }

        //object of class 
        unbounded_knapsack k = new unbounded_knapsack();
        k.output(v, w, W);
    }
}

Input:

We will input the number of items and the corresponding value and weight for each item. We also need to get the maximum capacity of our bag.

Output:

Enter number of items: 5

Enter Capacity: 50
Enter value 1:  140
Enter weight 1: 10
Enter value 2:  225
Enter weight 2: 15
Enter value 3:  80
Enter weight 3: 10
Enter value 4:  240
Enter weight 4: 20
Enter value 5:  120
Enter weight 5: 12

750.0
3 complete units of item 1 plus 5/15 units of item 1

Also read: Java Ternary operator with example