Knapsack Problem in Java

Posted By: Java Examples - 1:16 PM

Share

& Comment

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)

About Java Examples

I’m passionate about Web Development and Programming and I go to extreme efforts to meet my passion. I’m a believer of learning the fundamentals first. I try to understand everything little bit more than the average.

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .