Implementing 0-1 Knapsack in 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.

In 0-1 Knapsack, the restriction is that, one cannot select fraction of any item. He/She must select either whole item or try with alternate one.

//To implement knapsap zero/one problem
import java.io.*;
class knapo {
    void knapsack(int w[], int p[], int n, int m) {
        int s[][] = new int[n + 1][m + 1];
        for (int wt = 0; wt <= m; wt++)
            s[0][wt] = 0;
        for (int i = 0; i <= n; i++)
            s[i][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= m; j++) {
                if (w[i] <= j) {
                    if ((p[i] + s[i - 1][j - w[i]]) > s[i - 1][j])
                        s[i][j] = p[i] + s[i - 1][j - w[i]];
                    else
                        s[i][j] = s[i - 1][j];
                } else
                    s[i][j] = s[i - 1][j];
            }

        knapsack_items(s, n, m, w, p);
    }

    void knapsack_items(int s[][], int n, int m, int w[], int p[]) {
        int ans[] = new int[n + 1];
        int i = n;
        int k = m;
        int profit = 0;
        while (i > 0 && k > 0) {
            if (s[i][k] != s[i - 1][k]) {
                ans[i] = 1;
                profit += p[i];
                k = k - w[i];
            }
            i--;
        }

        System.out.println("values for element");
        for (i = 1; i <= n; i++)
            System.out.println("Element " + i + ":" + ans[i]);
        System.out.println("profit = " + profit);
    }
}

class knapmain {
    public static void main(String args[]) throws IOException {
        knapo ob = new knapo();

        BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("how many objects");
        int n = Integer.parseInt(obj.readLine());
        System.out.println("enter the capacity of bag");
        int m = Integer.parseInt(obj.readLine());
        int p[], w[];
        p = new int[n + 1];
        w = new int[m + 1];
        System.out.println("enter the profit and weight");
        for (int i = 1; i <= n; i++) {
            System.out.print("P" + i + ":");
            p[i] = Integer.parseInt(obj.readLine());
            System.out.print("W" + i + ":");
            w[i] = Integer.parseInt(obj.readLine());
            System.out.println();

        }
        ob.knapsack(w, p, n, m);

    }
}
/* output

how many objects
4
enter the capacity of bag
15
enter the profit and weight
P1:5
W1:6

P2:8
W2:9

P3:5
W3:6

P4:4
W4:7

Values for elements
Element 1:1
Element 2:1
Element 3:0
Element 4:0

profit = 13
Process Exit...
*/

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.