top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Knapsack problem with size 50?

+1 vote
579 views

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.

posted May 9, 2014 by As M Ob

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

0 votes

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 :)

answer May 9, 2014 by Salil Agrawal
Sorry this is DP, wait for some time I will provide the link for the greedy solution.
0 votes

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.

answer May 9, 2014 by Salil Agrawal
Similar Questions
+2 votes

suppose we have an array of N natural numbers and asks him to solve the following queries:-
Query a:- modify the element present at index i to x.
Query b:- count the number of even numbers in range l to r inclusive.
Query c:- count the number of odd numbers in range l to r inclusive.

input:
First line of the input contains the number N. Next line contains N natural numbers.Next line contains an integer Q followed by Q queries.
a x y - modify the number at index x to y.
b x y - count the number of even numbers in range l to r inclusive.
c x y - count the number of odd numbers in range l to r inclusive.
I tried to solve using simple arrays but it isn't doing well for big constraints so I thought to use other DS with efficient algorithm so please explain appropriate algorithm.Thanks in advance.

+2 votes

Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that they sum up to S.

+4 votes

Given a binary matrix, find out the maximum size square sub-matrix with all 1 s, Recusively

For example, consider the below binary matrix.
(Source:- geeksforgeeks

   0  1  1  0  1 
   1  1  0  1  0 
   0  1  1  1  0
   1  1  1  1  0
   1  1  1  1  1
   0  0  0  0  0

The maximum square sub-matrix with all set bits is

1  1  1
1  1  1
1  1  1

As we know it's general solution is with DP, but here i am interested in Recursive Approach

+1 vote

Given an array of denominations and array Count , find minimum number of coins required to form sum S.

for example:

  coins[]={1,2,3};
  count[]={1,1,3};

i.e we have 1 coin of Rs 1 , 1 coin of Rs 2 , 3 coins of Rs 3.

Now if we input S = 6 then output should be 2 with possible combination : 3+3 = 6

...