Fractional Knapsack Problem Solution [Fractional Knapsack][Java]

This program solves the fractional knapsack problem.

The problem :

There are n items in a store. For i =1,2, . . . , n, item i has weight w_i > 0 and worth v_i > 0. Thief can carry a maximum weight of W pounds in a knapsack. In this version of a problem the items can be broken into smaller piece, so the thief may decide to carry only a fraction x_i of object i, where 0 ≤ x_i ≤ 1. Item i contributes x_iw_i to the total weight in the knapsack, and x_iv_i to the value of the load.
In Symbol, the fraction knapsack problem can be stated as follows.
maximize ⁿS_i=1 x_iv_i subject to constraint ⁿS_i=1 x_iw_i ≤ W
It is clear that an optimal solution must fill the knapsack exactly, for otherwise we could add a fraction of one of the remaining objects and increase the value of the load. Thus in an optimal solution ⁿS_i=1 x_iw_i = W.

The fractional knapsack problem solution is based on the greedy approach where the best-looking step is taken at each choice. (In this case, the highest ratio item is selected from all the items).

Code:

import java.util.Scanner;

public class FractionalKnapsack {

    double weight[];
    double benefit[];
    double ratio[];
    double W;

    FractionalKnapsack() {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the number of items in the store: ");
        int nItems = scan.nextInt();
        System.out.println("Enter the (weight and benefit) of items: ");
        weight = new double[nItems];
        benefit = new double[nItems];
        ratio = new double[nItems];

        for (int i = 0; i < nItems; ++i) {
            weight[i] = scan.nextDouble();
            benefit[i] = scan.nextDouble();
            ratio[i] = benefit[i] / weight[i]; 
        }

        System.out.println("Enter the weight of the knapsack: ");
        W = scan.nextDouble();
    }

    int getNext() {
        double highest = 0;
        int index = -1;
        for (int i = 0; i < benefit.length; ++i) {
            if (ratio[i] > highest) {
                highest = ratio[i];
                index = i;
            }
        } 
        return index;
    }

    void fill() {
        double cW = 0; //current weight
        double cB = 0; //current benefit 

        System.out.print("\nItems considered: ");
        while (cW < W) {
            int item = getNext();        //next highest ratio
            if (item == -1) {
                //No items left
                break;
            }

            System.out.print((item+1)+" ");
            if (cW + weight[item] <= W) {
                cW += weight[item];
                cB += benefit[item];
                //mark as used for the getNext() (ratio) function
                ratio[item] = 0;
            } else {
                cB += (ratio[item] * (W - cW));
                cW += (W - cW);
                break;  //the knapsack is full
            }
        }
        System.out.println("\nMax Benefit = " + cB + ", Max Weight = " + cW);
    }

    public static void main(String[] args) {
        FractionalKnapsack fk = new FractionalKnapsack();
        fk.fill();
    }
}

Output:

Enter the number of items in the store:
5
Enter the (weight and benefit) of items:
20 4
40 3
10 1
35 5
40 2
Enter the weight of the knapsack:
50

Items considered: 1 4
Max Benefit = 8.285714285714285, Max Weight = 50.0

01 Knapsack Problem : Finding a solution through Dynamic Programming [Java][01Knapsack][Dynamic Programming]

This program finds a solution for a given 01 Knapsack Problem. The solution is based on Dynamic programming. So the time complexity for this program is O(nW). n is the number of items and W is the maximum size of the knapsack. This algorithm is more efficient than the one that uses brute force (checking all the possible combinations). That one has a complexity of O(2^n) [exponential].

Code:

import java.util.Arrays;
import java.util.Scanner;

public class Knapsack01Dynamic {

    int[][] table;
    int[] weight;
    int[] benefit;
    int capacityKnapsack;
    int nItems;

    Scanner scan = new Scanner(System.in);

    int B(int items, int maxCapacity) {

        if (maxCapacity < 0 || items < 0) {
            return -2;
        }

        if (table[items][maxCapacity] != -1) {
            return table[items][maxCapacity];
        }

        int arg1 = B(items - 1, maxCapacity);
        int arg2 = B(items - 1, (maxCapacity - weight[items - 1]));
        if (arg2 == -2) {
            arg2 = 0;
        } else {
            arg2 += benefit[items - 1];
        }
        table[items][maxCapacity] = Math.max(arg1, arg2);
        return table[items][maxCapacity];
    }

    void printItems() {
        System.out.println("Max benefit: "+table[nItems][capacityKnapsack]);
        System.out.println("Items in the knapsack: ");
        int row = capacityKnapsack;
        for (int i = nItems; i > 0; --i) {

            if (table[i][row] != table[i - 1][row]) {
                System.out.print(i+" ");
                row -= weight[i - 1];
            }
        }
    }   
    
    void input() {
        System.out.println("Enter the number of items: ");
        nItems = scan.nextInt();

        System.out.println("Enter the (weight and benefit)s of the n items: ");

        weight = new int[nItems];
        benefit = new int[nItems];

        for (int i = 0; i < nItems; ++i) {
            weight[i] = scan.nextInt();
            benefit[i] = scan.nextInt();
        }

        System.out.println("Max capacity of the knapsack: ");
        capacityKnapsack = scan.nextInt();
        table = new int[nItems + 1][capacityKnapsack + 1];

        for (int i = 1; i < nItems + 1; ++i) {
            Arrays.fill(table[i], -1);
        } 
        for (int i = 0; i < nItems + 1; ++i) {
            table[i][0] = 0;
        }
    }

    void printTable() {
        System.out.println();
        System.out.print("   ");
        int count = 0;
        for (int i = 0; i < capacityKnapsack + 1; ++i) {
            System.out.printf("%3d ", i);
        }
        System.out.println("\n");
        for (int i = 0; i < nItems + 1; ++i) {
            System.out.printf("%-3d", count);
            for (int j = 0; j < capacityKnapsack + 1; ++j) {
                System.out.printf("%1$3d ", table[i][j]);
            }
            count++;
            System.out.println();
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        Knapsack01Dynamic kd = new Knapsack01Dynamic();
        kd.input();
        kd.B(kd.nItems, kd.capacityKnapsack);
        kd.printTable(); 
        kd.printItems();
    }
}

Sample Output :

Enter the number of items:
4
Enter the (weight and benefit)s of the n items:
2 3
3 4
4 5
5 6
Max capacity of the knapsack:
5

     0   1   2   3   4   5

0    0   0   0   0   0   0
1    0   0   3  -1  -1   3
2    0   0  -1  -1  -1   7
3    0  -1  -1  -1  -1   7
4    0  -1  -1  -1  -1   7

Max benefit: 7
Items in the knapsack:
2 1

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