Knapsack problem with size 50?

Question

Please help me to solve the Knapsack problem using greedy algorithms.

  Profit Weight    
1) 30    10
2) 50    5
3) 20    12
4) 70    40
5) 90    15

The knapsack size is 50. Make the selection criteria based on : min weight, max profit and Ratio.

Answer 1

This can easily be solved by the solution provided at WikiPedia (http://en.wikipedia.org/wiki/Knapsack_problem ).

Here is the pseudo code

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for j from 0 to W do
  m[0, j] := 0
end for 
for i from 1 to n do
  for j from 0 to W do
    if w[i] <= j then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
    else
      m[i, j] := m[i-1, j]
    end if
  end for
end for

In your case

W(knapsack Capacity) = 50, 
n(Number of distinct items) = 5

Now job is converting this pseudo-code to real working code i.e. that is your homework :)

Comments

Sorry this is DP, wait for some time I will provide the link for the greedy solution.

Answer 2

OK I found the Greedy Approach I am just giving the algo you need to write the code -
Step 1: Convert all the numbers in Profit/Weight ratio
i.e. 1) 30/10 = 3
2) 50/5 = 10
3) 20/12 = 1.66
4) 70/40 = 1.75
5) 90/15 = 6
Step 2: Now sort them in decreasing order of ratio i.e. 10, 6, 3, 1.75, 1.66
Step 3: Pick in the order till total weight is less then KnapSack limit. At the border you need to backtrack and rerun the algo with the remaining one but in this example that may not be required.