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...
*/