Time complexity of 0/1 Knapsack challenge

Question

The code gives correct output. How do I calculate time complexity for code like this?

The program finds all the combinations of items and sees if the combination gives the max profit. If the last item can't be added or there are no more items left, it checks to see if this value of knapsack is maximum or not.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Item {

    static int id = 0;
    int weight;
    int cost;
    double ratio;
    int itemNo = id++;

    public Item(int weight, int cost) {
        this.weight = weight;
        this.cost = cost;
        this.ratio = (double) cost / weight;
    }

    public String toString() {
        return itemNo + "";
    }
}

class Store {

    int nItems;
    List<Item> store = new ArrayList<>();

    Item getNextHighestRatioItem() {
        int i = -1;
        double highestRatio = Double.MIN_VALUE;
        for (int j = 0; j < store.size(); ++j) {
            double thisRatio = store.get(j).ratio;
            if (thisRatio > highestRatio) {
                i = j;
                highestRatio = thisRatio;
            }
        }
        return store.get(i);
    }
}

class Knapsack {

    Knapsack(int nItems, int maxWeight) {
        this.maxWeight = maxWeight;
        this.knapsack = new boolean[nItems];
    }

    boolean[] knapsack;
    int maxWeight = 50;
    int weight;
    int worth;

    public boolean addItem(Item item) {
        if (weight + item.weight > maxWeight) {
            return false;
        }
        knapsack[item.itemNo] = true;
        weight += item.weight;
        worth += item.cost;
        return true;
    }

    public void removeItem(Item item) {
        knapsack[item.itemNo] = false;
        weight = weight - item.weight;
        worth -= item.cost;
    }

    public boolean isFull() {
        return weight == maxWeight;
    }
}

public class Knapsack01 {

    int knapsackCapacity, nItems;
    Store storeInstance;
    Knapsack knapsackInstance;
    Scanner scan = new Scanner(System.in);

    Knapsack01() {
        System.out.println("Enter the size of the knapsack ");
        knapsackCapacity = scan.nextInt();
        storeInstance = new Store();

        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the number of items: ");
        nItems = scan.nextInt();

        int weight, cost, ratio;
        for (int i = 0; i < nItems; ++i) {
            System.out.println("Enter item " + (i + 1) + "'s weight and cost: ");
            weight = scan.nextInt();
            cost = scan.nextInt();

            Item item = new Item(weight, cost);
            storeInstance.store.add(item);
        }

        knapsackInstance = new Knapsack(nItems, knapsackCapacity);
    }

    public void printSolution(int runningMax) {
        System.out.println("\nFound a better solution, worth : " + runningMax + "\nItems: ");
        //Print knapsack contents
        for (int j = 0; j < knapsackInstance.knapsack.length; ++j) {
            if (knapsackInstance.knapsack[j] == true) {
                System.out.print((j + 1) + " ");
            }
        }
    }

    int runningMax = 0;
    public void combinations(int callingIndex) {

        for (int i = callingIndex; i < knapsackInstance.knapsack.length; ++i) {
            if (knapsackInstance.knapsack[i] == true) {
                continue;
            }
            if (knapsackInstance.addItem(storeInstance.store.get(i))) {
                combinations(i);

                //Check worth only if the item has been added and it is the last item [no more items to add]
                if (i == knapsackInstance.knapsack.length - 1) { 
                    if (knapsackInstance.worth > runningMax) {
                        runningMax = knapsackInstance.worth;
                        printSolution(runningMax);
                    }
                    knapsackInstance.removeItem(storeInstance.store.get(i));
                    return;
                }
                knapsackInstance.removeItem(storeInstance.store.get(i));
            } else {    //or if the next item couldn't be added as the knapsack was already full
                if (knapsackInstance.worth >= runningMax) {
                    runningMax = knapsackInstance.worth;
                    printSolution(runningMax);
                }
            }
        }
    }

    public static void main(String[] args) {
        Knapsack01 kp = new Knapsack01();
        kp.combinations(0);
    }
}

Answer 1

I don't know, but I'm afraid it's still exponential. Let's make a Gedankenexperiment: Take 1000 items with weight = cost = 1 and knapsack capacity = 1000. Will it ever terminate or will it try all 2**1000 possibilities? I don't know, but I'm sceptical.

That said, it looks much better now. I'd bet it's also way faster.

---

Some general comments: You're repeating this snippet

if (knapsackInstance.worth >= runningMax) {
    runningMax = knapsackInstance.worth;
    printSolution(runningMax);
}

and you don't have to. These two lines below the first occurrence are useless:

knapsackInstance.removeItem(storeInstance.store.get(i));
return;

This is suspect:

if (knapsackInstance.knapsack[i] == true) {
    continue;
}

Does it ever happen? I guess no, and then I'd replace it by

assert !knapsackInstance.knapsack[i];

See Programming With Assertions.

Btw., test like x==true and x==false are code pollution.

---

int weight, cost, ratio;

Please no. This is no pascal. Define all variables as late as possible (minimize scope) and ideally initialize them in the definition.

ratio seems to be unused. Switch warnings on and clean them. I sometimes keep one one or two in places which I want to clean up later, but never more.