Monday, September 8, 2014

01Knapsack Problem Solution [Recursion][Java]

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsackand must fill it with the most valuable items.

In 01 Knapsack problem, you can either take an item or just leave it, you can't take fractions of an item (like in Fractional Knapsack).

The solution finds all the combinations of the items (check out how to find combinations of all characters in a string : http://coderbots.blogspot.com/2014/09/printing-all-possible-character.html  This code is used here] that can be added to the knapsack and checks if it has greater value than some previous max value. If so, it prints the max value and sets the new value as the maximum running value.

[Note: This is a recursive solution to the problem. Time Complexity ~2^n. There is a dynamic programming based solution with Complexity O(nW) too.]

Code:


/* 
 *@author Jatin Thakur coderbots.blogspot.com
 */
 
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);
    }
}

Output #1:

Enter the size of the knapsack 
50
Enter the number of items: 
3
Enter item 1's weight and cost: 
10 20
Enter item 2's weight and cost: 
20 100
Enter item 3's weight and cost: 
30 120

Found a better solution, worth is now : 120
Items: 
1 2 
Found a better solution, worth is now : 140
Items: 
1 3 
Found a better solution, worth is now : 220
Items: 
2 3

Output #2:

Enter the size of the knapsack
6404180
Enter the number of items:
24
Enter item 1's weight and cost:
382745 825594
Enter item 2's weight and cost:
799601 1677009
Enter item 3's weight and cost:
909247 1676628
Enter item 4's weight and cost:
729069 1523970
Enter item 5's weight and cost:
467902 943972
Enter item 6's weight and cost:
44328 97426
Enter item 7's weight and cost:
34610 69666
Enter item 8's weight and cost:
698150 1296457
Enter item 9's weight and cost:
823460 1679693
Enter item 10's weight and cost:
903959 1902996
Enter item 11's weight and cost:
853665 1844992
Enter item 12's weight and cost:
551830 1049289
Enter item 13's weight and cost:
610856 1252836
Enter item 14's weight and cost:
670702 1319836
Enter item 15's weight and cost:
488960 953277
Enter item 16's weight and cost:
951111 2067538
Enter item 17's weight and cost:
323046 675367
Enter item 18's weight and cost:
446298 853655
Enter item 19's weight and cost:
931161 1826027
Enter item 20's weight and cost:
31385 65731
Enter item 21's weight and cost:
496951 901489
Enter item 22's weight and cost:
264724 577243
Enter item 23's weight and cost:
224916 466257
Enter item 24's weight and cost:
169684 369261

Found a better solution, worth is now : 11693411
Items:
1 2 3 4 5 6 7 8 9 10
Found a better solution, worth is now : 12742700
Items:
1 2 3 4 5 6 7 8 9 10 12
Found a better solution, worth is now : 12742700
Items:
1 2 3 4 5 6 7 8 9 10 12
Found a better solution, worth is now : 12742700
Items:
1 2 3 4 5 6 7 8 9 10 12
Found a better solution, worth is now : 12742700
Items:
1 2 3 4 5 6 7 8 9 10 12
Found a better solution, worth is now : 12742700
Items:
1 2 3 4 5 6 7 8 9 10 12
Found a better solution, worth is now : 12742700
Items:
1 2 3 4 5 6 7 8 9 10 12
Found a better solution, worth is now : 12742700
Items:
1 2 3 4 5 6 7 8 9 10 12
Found a better solution, worth is now : 12808431
Items:
1 2 3 4 5 6 7 8 9 10 12 20
Found a better solution, worth is now : 12808431
Items:
1 2 3 4 5 6 7 8 9 10 12 20
Found a better solution, worth is now : 12808431
Items:
1 2 3 4 5 6 7 8 9 10 12 20
Found a better solution, worth is now : 12808431
Items:
1 2 3 4 5 6 7 8 9 10 12 20
Found a better solution, worth is now : 12946247
Items:
1 2 3 4 5 6 7 8 9 10 13
Found a better solution, worth is now : 12946247
Items:
1 2 3 4 5 6 7 8 9 10 13
Found a better solution, worth is now : 12946247
Items:
1 2 3 4 5 6 7 8 9 10 13
Found a better solution, worth is now : 12946247
Items:
1 2 3 4 5 6 7 8 9 10 13
Found a better solution, worth is now : 12946247
Items:
1 2 3 4 5 6 7 8 9 10 13
Found a better solution, worth is now : 12946247
Items:
1 2 3 4 5 6 7 8 9 10 13
Found a better solution, worth is now : 12946247
Items:
1 2 3 4 5 6 7 8 9 10 13
Found a better solution, worth is now : 12946247
Items:
1 2 3 4 5 6 7 8 9 10 13
Found a better solution, worth is now : 12946247
Items:
1 2 3 4 5 6 7 8 9 10 13
Found a better solution, worth is now : 12946247
Items:
1 2 3 4 5 6 7 8 9 10 13
Found a better solution, worth is now : 12946247
Items:
1 2 3 4 5 6 7 8 9 10 13
Found a better solution, worth is now : 12953974
Items:
1 2 3 4 5 6 7 8 9 11 13 20
Found a better solution, worth is now : 12953974
Items:
1 2 3 4 5 6 7 8 9 11 13 20
Found a better solution, worth is now : 12953974
Items:
1 2 3 4 5 6 7 8 9 11 13 20
Found a better solution, worth is now : 12953974
Items:
1 2 3 4 5 6 7 8 9 11 13 20
Found a better solution, worth is now : 12957945
Items:
1 2 3 4 5 6 7 8 9 11 15 24
Found a better solution, worth is now : 13048168
Items:
1 2 3 4 5 6 7 8 9 11 22 23 24
Found a better solution, worth is now : 13066065
Items:
1 2 3 4 5 6 7 8 10 11 17 20 23
Found a better solution, worth is now : 13093491
Items:
1 2 3 4 5 6 7 8 10 16 20 22 24
Found a better solution, worth is now : 13133611
Items:
1 2 3 4 5 6 7 8 11 16 17 20 24
Found a better solution, worth is now : 13143195
Items:
1 2 3 4 5 6 7 9 10 11 20 23 24
Found a better solution, worth is now : 13188450
Items:
1 2 3 4 5 6 7 9 10 11 22 24
Found a better solution, worth is now : 13205590
Items:
1 2 3 4 5 6 7 9 10 16 17 20
Found a better solution, worth is now : 13205590
Items:
1 2 3 4 5 6 7 9 10 16 17 20
Found a better solution, worth is now : 13205590
Items:
1 2 3 4 5 6 7 9 10 16 17 20
Found a better solution, worth is now : 13205590
Items:
1 2 3 4 5 6 7 9 10 16 17 20
Found a better solution, worth is now : 13242006
Items:
1 2 3 4 5 6 7 9 11 16 23 24
Found a better solution, worth is now : 13305158
Items:
1 2 3 4 5 6 7 10 11 16 17
Found a better solution, worth is now : 13305158
Items:
1 2 3 4 5 6 7 10 11 16 17
Found a better solution, worth is now : 13305158
Items:
1 2 3 4 5 6 7 10 11 16 17
Found a better solution, worth is now : 13305158
Items:
1 2 3 4 5 6 7 10 11 16 17
Found a better solution, worth is now : 13305158
Items:
1 2 3 4 5 6 7 10 11 16 17
Found a better solution, worth is now : 13305158
Items:
1 2 3 4 5 6 7 10 11 16 17
Found a better solution, worth is now : 13305158
Items:
1 2 3 4 5 6 7 10 11 16 17
Found a better solution, worth is now : 13307916
Items:
1 2 3 4 6 7 10 11 13 16 24
Found a better solution, worth is now : 13373421
Items:
1 2 3 4 6 7 10 11 16 17 20 22 24
Found a better solution, worth is now : 13394770
Items:
1 2 4 5 6 7 9 10 11 13 17 20 23 24
Found a better solution, worth is now : 13468374
Items:
1 2 4 5 6 7 9 10 11 16 23 24
Found a better solution, worth is now : 13524340
Items:
1 2 4 5 6 7 10 11 13 16 17 20 22
Found a better solution, worth is now : 13524340
Items:
1 2 4 5 6 7 10 11 13 16 17 20 22
Found a better solution, worth is now : 13549094
Items:
1 2 4 5 6 10 11 13 16 22 23 24

No comments:

Post a Comment