# 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

#### 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`