### Knapsack Problem in Java

Knapsack problem :
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count 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 knapsack and must fill it with the most useful items.
 Knapsack in Wikipedia
Algorithm is Given bellow :
GreedyKnapsack (m, n)
//p and w are arrays contain the profits and weights respectively of
// n objects ordered such that p[i]/w[i] >= p[i+1]/w[i+1]
// that is in non-increasing order.
// m is the knapsack size and x is the solution vector
for i < 1 to n do
x[i]ÃŸ 0
endFor
total ÃŸ m
for i ! 1 to n do
if (w[i] <= total)
x[i]ÃŸ1
totalÃŸtotal-w[i]
else break // to exit the for-loop
Endif
endFor

if (i<=n) x[i] ÃŸ total/w[i]

endGreedyKnapsack

Java version of the  Greedy Knapsack  is given below:

```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package knapsack;

/**
*
* @author ACHCHUTHAN
*/
public class GreedyKnapsack  {

double[] profit;
double[] weight;
double[] take;

public GreedyKnapsack(int n) {

profit = new double[n];
weight = new double[n];
take = new double[n];
for (int i = 0; i < n; i++) {
profit[i] = (int) Math.round(Math.random() * 96 + 44);
weight[i] = (int) Math.round(Math.random() * 89 + 15);
}
}

public void unitPriceOrder() {
for (int i = 0; i < profit.length; i++) {
for (int j = 1; j < (profit.length - i); j++) {
double x=profit[j - 1] / weight[j - 1];
double y=profit[j] / weight[j];
if (x <=y) {
double temp = profit[j - 1];
profit[j - 1] = profit[j];
profit[j] = temp;

double temp1 = weight[j - 1];
weight[j - 1] = weight[j];
weight[j] = temp1;
}
}
}
}

public void Knapsack(int m) {
unitPriceOrder();
int j;
for (j = 0; j < profit.length; j++) {
take[j] = 0;
}
double total = m;
for (j = 0; j < profit.length; j++) {
if (weight[j] <= total) {
take[j] = 1.00;
total = total - weight[j];
} else {
break;// to exit the for-loop
}
}
if (j < profit.length) {
take[j] = (double)(total / weight[j]);
}
}

public void print() {

System.out.println("item" + " |  " + "profit" + "  |   " + "weight" +
"   |     " + "Unit Price" + "      |" + "  Take weight");
for (int n = 0; n < profit.length; n++) {
System.out.println(n + "\t" + profit[n] + "\t" + weight[n] + "\t"
+ (profit[n] / weight[n]) + "\t" + take[n]);
}
}

public static void main(String args[]) {
GreedyKnapsack G = new GreedyKnapsack(10);
System.out.println("Optimal soluation to knapsack instance "
+ "with values given as follows : m=35");
G.Knapsack(35);
G.print();
System.out.println("=======+============+=======+============+="
+ "===========");
System.out.println("Optimal soluation to knapsack instance with "
+ "values given as follows : m=120");
G.Knapsack(120);
G.print();
}
}

```
Output of this program is given bellow :
run:
Optimal soluation to knapsack instance with values given as follows : m=35

```item |  profit  |   weight   |     Unit Price      |  Take weight
0        92.0        17.0        5.411764705882353        1.0
1        113.0       61.0        1.8524590163934427      0.295081                                                      96721311475
2        65.0        41.0        1.5853658536585367        0.0
3        139.0       96.0        1.4479166666666667        0.0
4        101.0       70.0        1.4428571428571428        0.0
5        66.0        59.0        1.11864406779661          0.0
6        79.0        76.0        1.0394736842105263        0.0
7        64.0        74.0        0.8648648648648649        0.0
8        84.0        98.0        0.8571428571428571        0.0
9        47.0        93.0        0.5053763440860215        0.0
=======+============+=======+============+=======+============
Optimal soluation to knapsack instance with values given as follows : m=120
item |  profit  |   weight   |     Unit Price      |  Take weight
0        92.0        17.0        5.411764705882353        1.0
1        113.0       61.0        1.8524590163934427       1.0
2        65.0        41.0        1.5853658536585367       1.0
3        139.0       96.0        1.4479166666666667       0.01041                                                    6666666666666
4        101.0       70.0        1.4428571428571428       0.0
5        66.0        59.0        1.11864406779661         0.0
6        79.0        76.0        1.0394736842105263       0.0
7        64.0        74.0        0.8648648648648649       0.0
8        84.0        98.0        0.8571428571428571       0.0
9        47.0        93.0        0.5053763440860215       0.0
BUILD SUCCESSFUL (total time: 0 seconds)
```