Java Program to Solve 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.

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 Program to Solve Knapsack Problem


When you run the program, the output will be:

Optimal soluation to knapsack instance with values given as follows : m=35
item |  profit  |   weight   |     Unit Price      |  Take weight
0    138.0    24.0    5.75    1.0
1    114.0    24.0    4.75    0.4583333333333333
2    56.0    17.0    3.2941176470588234    0.0
3    101.0    51.0    1.9803921568627452    0.0
4    125.0    64.0    1.953125    0.0
5    95.0    49.0    1.9387755102040816    0.0
6    124.0    86.0    1.441860465116279    0.0
7    55.0    41.0    1.3414634146341464    0.0
8    93.0    89.0    1.0449438202247192    0.0
9    52.0    103.0    0.5048543689320388    0.0

Previous Post Next Post