# 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[wt] = 0;
for (int i = 0; i <= n; i++)
s[i] = 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();

System.out.println("how many objects");
System.out.println("enter the capacity of bag");
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 + ":");
System.out.print("W" + i + ":");
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...
*/
```

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