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.

Knapsack in Wikipedia

Algorithm:

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