# Knapsack problem with size 50?

+1 vote
135 views

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

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

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

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

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.

Similar Questions

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.

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.

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