Is this algorithm efficient for the 01Knapsack?

Question

This code uses recursion to solve the 01Knapsack problem. It evaluates all the item permutations that can be added to the knapsack and checks if it gives the maximum profit. What else could have been used to get a faster solution?

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

class Item {

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

    boolean taken = false;

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

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

class Store {

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

    public Store() {
        takeInput();
    }

    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);
    }

    public void takeInput() {

        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the number of items: ");
        int 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);
            store.add(item);
        }
    }

    public int getSize() {
        return store.size();
    }
}

class Knapsack {

    Set<Item> knapsack = new HashSet<>();
    int maxWeight = 50;
    int weight;

    public boolean addItem(Item item) {
        if (weight + item.weight > maxWeight) {
            return false;
        }
        knapsack.add(item);
        weight += item.weight;
        return true;
    }

    public void removeItem(Item item) {
        knapsack.remove(item);
        weight = weight - item.weight;
    }

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

    public int calculateTotalWorth() {
        int sum = 0;
        for (Item item : knapsack) {
            sum += item.cost;
        }
        return sum;
    }

}

public class KnapsackProblem01 {

    Store store = new Store();
    Knapsack knapsack = new Knapsack();

    int worth = 0;

    public void fillKnapsack() {

        int thisWorth = knapsack.calculateTotalWorth();
        if (thisWorth > worth) {
            worth = thisWorth;
            System.out.println("Found a better solution " + worth);
            System.out.println("Knapsack has items: ");
            for (Item i : knapsack.knapsack) {
                System.out.print(i + " ");
            }
        }

        if (knapsack.isFull()) {
            return;
        }

        for (Item i : store.store) {
            if (i.taken) {
                continue;
            }
            if (knapsack.addItem(i)) {
//                System.out.println("Added item "+i+" to the knapsack");
                i.taken = true;
                fillKnapsack();
                knapsack.removeItem(i);
//                System.out.println("Removed item "+i+" from the knapsack");
                i.taken = false;
            }
        }
    }

    public static void main(String[] args) {
        KnapsackProblem01 kp = new KnapsackProblem01();
        kp.fillKnapsack();
    }
}

Answer 1

It's no way optimal. Looking at the wiki, there are algorithms using dynamic programming, which are surely faster.

The other thing is fooling around with a HashSet. It's a nice and fast data structure, but all you need is a boolean[], which is an order of magnitude faster. And it also makes it all simpler.

Item#taken is not a good idea. It should a property of the knapsack, the item doesn't really care. Imagine, you'd parallelize your program, then you'd need an immutable Item.

calculateTotalWorth should be replaced by an incremented computation the way weight gets computed.

The knapsack.worth should only be checked when no item fits. Otherwise, you know that it's not optimal yet.