Fractional Knapsack

Question

This is my solution to an assignment on the fractional Knapsack problem. I take as problem input the following pieces of information:

• The number of item types
• The total weight limit
• For each item type, the total available weight of that item type and the value per unit of weight

The output is the amount of weight to select of each item type that maximizes the total value subject to the weight constraint. The program works fine, but I wanted to understand what could have been better with the code.

import java.util.List;
import java.util.LinkedList;
import java.util.Scanner;

public class Knapsack {

// This will define the length of the arrays, numOfItems and wholeValue;
int arrayLength;   // The number of items to be entered. 

int totalQty;      // The total Quantity that we must check against.
int[] numOfItems;  // Holds the quantity
int[] wholeValue; // Holds the value


// This is the list that keeps the weight (value/quantity) for each item
// and its index in either array numOfItems / wholeValue. 
// The index is useful to retrieve the quantity later on. 
// The array wholeValue has no use after the weights have been calculated.
class weightsAndIndex{
    double Weight;
    int Index;

}

List<weightsAndIndex> myObj;

// Initialise all the values.
public Knapsack(int n, int m)
{
    numOfItems = new int[n];
    wholeValue = new int[n];
    arrayLength = n;
    totalQty = m;
    myObj = new LinkedList<>();

}

// Sort the weights as value/quantity.
public void sortWeights()
{
    double max;
    double temp;
    int i = 0;
    int index=0;
    weightsAndIndex tmpObj;

    for (i = 0; i < arrayLength; i++)
    {
        // Calculate the weight of all the items in a loop
        temp = (double)wholeValue[i]/(double)numOfItems[i];
        // Create a new object to store the weight and the index
        tmpObj = new weightsAndIndex();
        tmpObj.Index = i;
        tmpObj.Weight = temp;

        // Find the sorted position of the current weight in the list.
        while (index <= myObj.size() -1 && myObj.get(index).Weight > temp)
        {
            index++;
        }
        // Add the object at the index location to the list.
        myObj.add(index, tmpObj);
        // Reset the index to start from the start again.
        index = 0;
    }

}

public int min(int x, int y)
{
    if (x < y)
        return x;
    return y;
}
public double findFinalWeight ()
{
    double tmp;
    int tempIndex; 
    int numAtIndex;
    double finalWeight = 0;
    int tempMin;
    int qty = totalQty;
    boolean exceeded = false;

    for (int i = 0; i < arrayLength && exceeded != true; i++)
    {
        // We start with the heaviest weight. 
        // We need to get the corresponding index entry to access its quantity
        tempIndex = myObj.get(i).Index;
        numAtIndex = numOfItems[tempIndex];
        // Between the quantity yet to be filled and the quantity corresponding to this weight, 
        // we can only serve the minimum of the two. 
        // Effectively, if we have 50 quantities yet to be filled but only 30 of "this" item, 
        // we can serve up only 30. 
        tempMin = min(qty, numAtIndex); 
        // Add the quantity. 
        finalWeight = finalWeight + myObj.get(i).Weight * tempMin;  
        if (qty == tempMin)
        {
            exceeded = true;
        }
        else
        {
            qty = qty - tempMin;
        }

    }

    return finalWeight;
}

public static void main(String[] args) {
    // TODO Auto-generated method stub

    int totalNum;
    int totalVal;
    Scanner in = new Scanner(System.in);
    totalNum = in.nextInt();
    totalVal = in.nextInt();
    Knapsack obj = new Knapsack(totalNum, totalVal);



    // Read next set of inputs 
    for (int i = 0; i < obj.arrayLength; i++)
    {

        obj.wholeValue[i] = in.nextInt();
        obj.numOfItems[i] = in.nextInt();
    }

    obj.sortWeights();
    System.out.println(obj.findFinalWeight());


}
}

Answer 1

public class Knapsack {

Is this a knapsack? Or is it the parameters for an instance of the Knapsack problem? If the latter, it should be named something like KnapsackProblem.

int arrayLength;   // The number of items to be entered. 

You don't need to store an array length separately. Both numOfItems.length and wholeValue.length have this value.

int[] numOfItems;  // Holds the quantity
int[] wholeValue; // Holds the value

Why not store both of these in one collection?

    private class ItemType implements Comparator<ItemType> {
        int count;
        int totalWeight;
        double itemWeight;

        ItemType(int count, int totalWeight) {
            this.count = count;
            this.totalWeight = totalWeight;
            itemWeight = totalWeight / (double)count;
        }

        public double getItemWeight() {
            return itemWeight;
        }

        @Override
        public int compare(ItemType o1, ItemType o2) {
            return Double.compare(o2.getItemWeight(), o1.getItemWeight());
        }
    }

    private ItemType[] itemTypes;

I also added another level of indent. As a general rule, you want to have the contents of the class indented from where the class name is. Of course, that could have been a copy/paste error. Note that Ctrl + K will indent an entire block at once for you if there is at least one line in the block without indent.

And I marked the field as private as is usually appropriate for object fields.

Later, you have

    numOfItems = new int[n];
    wholeValue = new int[n];
    arrayLength = n;

which could be just

        itemTypes = new ItemType[n];

The original code expanded one input into three variables. This takes one input and uses it to initialize one variable.

    myObj = new LinkedList<>();

What is a myObj? I have no idea looking at this line. If it were called weightsAndIndexes, then I'd have a better idea. But actually, I think that we could do without it.

Rather than creating a new object to hold the unit weights, note that I put that in the new class. So we could just sort in place:

        java.util.Arrays.sort(itemTypes);

No new method needed. Note that this does require that ItemType implement the Comparable interface.

But if you do want to reinvent the wheel, let's look at the method.

    double max;

You never use this, so get rid of it.

    double temp;
    int i = 0;
    int index=0;
    weightsAndIndex tmpObj;

You only use these in the loop and the values don't carry over between iterations (except i). So declare them inside the loop. I'll show you where later.

    for (i = 0; i < arrayLength; i++)

I'd just say

    for (int i = 0; i < wholeValue.length; i++)

You should only predeclare your loop variable if you want to use it again after the loop is done. You don't, so stick with the standard loop declaration.

As I suggested earlier, you don't need arrayLength.

        temp = (double)wholeValue[i]/(double)numOfItems[i];

And now we can declare and initialize at the same time.

        double weight = (double)wholeValue[i]/(double)numOfItems[i];

Also, change the name. We know what this is. So no need for a generic name.

        tmpObj = new weightsAndIndex();

Again, combine declaration and initialization.

        WeightAndIndex weightAndIndex = new WeightAndIndex();

I also changed the names of both variable and type. In Java, class names are in StudlyCase while variables are in camelCase. Also, there is only one weight per object, so no need for the name to be plural.

Again, we know what this is, so we don't need a generic name for it.

        while (index <= myObj.size() -1 && myObj.get(index).Weight > temp)
        {
            index++;
        }
        // Add the object at the index location to the list.
        myObj.add(index, tmpObj);
        // Reset the index to start from the start again.
        index = 0;

This is more complicated than it needs to be. Let's rename myObj to weightIndexes.

        int index = 0;
        for (WeightAndIndex weightIndex : weightIndexes) {
             // if the current element is smaller or equal to the weight we're adding
             // we've found where it belongs, so end the loop
             if (weightIndex.weight <= weight) {
                 break;
             }

             index++;
        }

        weightIndexes.add(index, weightAndIndex);

Again, we move declaration and initialization to the same spot. We no longer need to reset the index, as we only set it when we need it.

Using the for each form means that we don't have to manually check if we're done yet nor get the correct element. It handles that for us.

We can't keep the weight check in the loop declaration with the for each form, so we move it into the loop and break out if the original check is not true (since it used to stay in if the check was true).

Moving on to findFinalWeight in the original.

    double tmp;

Unused.

    int tempIndex; 
    int numAtIndex;

Unnecessary.

    int tempMin;

Could be declared inside the loop.

    boolean exceeded = false;

Unnecessary.

    for (int i = 0; i < arrayLength && exceeded != true; i++)

This is an even better candidate for the for each form. You never use i except with get(i). So

    for (WeightAndIndex weightAndIndex : weightIndexes)

and moving on

        // We need to get the corresponding index entry to access its quantity
        tempIndex = myObj.get(i).Index;
        numAtIndex = numOfItems[tempIndex];
        // Between the quantity yet to be filled and the quantity corresponding to this weight, 
        // we can only serve the minimum of the two. 
        // Effectively, if we have 50 quantities yet to be filled but only 30 of "this" item, 
        // we can serve up only 30. 
        tempMin = min(qty, numAtIndex); 

By using weightAndIndex, we make this easier.

        // limit quantity to the remaining capacity of the knapsack
        int quantity = Math.min(capacity, numOfItems[weightAndIndex.Index]);

Declare and initialize at the same time. Also change name to be more descriptive. I'd also consider changing qty to capacity.

As mentioned in a comment on the question, you don't need to create your own min function. Java provides Math.min for you.

        finalWeight = finalWeight + myObj.get(i).Weight * tempMin;

This would be more idiomatic as

        finalWeight += weightAndIndex.Weight * quantity;

The += operator adds and stores the result.

        if (qty == tempMin)
        {
            exceeded = true;
        }
        else
        {
            qty = qty - tempMin;
        }

You could just say

        if (capacity <= quantity) 
        {
            break;
        }

        capacity -= quantity;

or

        capacity -= quantity;
        if (capacity <= 0) 
        {
            break;
        }

which is clearer about what it's checking.

Again, the -= subtracts and assigns in one operator.

The break ends the loop.

And if you change to itemTypes, then it's even easier.

        double cumulativeWeight = 0.0;
        int capacity = totalQty;
        for (ItemType itemType : itemTypes)
        {
            int quantity = Math.min(capacity, itemType.getQuantity());
            cumulativeWeight += quantity * itemType.getItemWeight();
            capacity -= quantity;
            if ( capacity <= 0)
            {
                break;
            }
        }

        return cumulativeWeight;

No more dereferencing arrays, just a simple iteration.

    // TODO Auto-generated method stub

The point of this is to remind you to fill in the details of the method. Once you've done that, you should delete this line.

    int totalNum;
    int totalVal;
    Scanner in = new Scanner(System.in);
    totalNum = in.nextInt();
    totalVal = in.nextInt();
    Knapsack knapsack = new Knapsack(totalNum, totalVal);

Again, there's no reason to separate declaration and initialization.

    Scanner in = new Scanner(System.in);
    int totalNum = in.nextInt();
    int totalVal = in.nextInt();
    Knapsack knapsack = new Knapsack(totalNum, totalVal);

Although you can shorten to

    Scanner in = new Scanner(System.in);
    Knapsack knapsack = new Knapsack(in.nextInt(), in.nextInt());

You don't need to create separate variables. Just store the necessary information directly.

    for (int i = 0; i < obj.arrayLength; i++)
    {

        obj.wholeValue[i] = in.nextInt();
        obj.numOfItems[i] = in.nextInt();
    }

This is fine for your original version, but if you change to itemTypes, you can rewrite it like

        inputItemTypes(in);

and

    public void inputItemTypes(Scanner in)
    {
        for (int i = 0; i < itemTypes.length; i++)
        {
            itemTypes[i] = new ItemType(in.nextInt(), in.nextInt());
        }
    }

This will work even if your main method is not in the same scope as your class.