MadeEasyAlgo

Question

Maximum profit using 0/1 Knapsack with W=200

 is there any other than brute force method to solve this??? or we have to do only with tabular method?please solve and mention the way that is efficient w.r.t time if any.

 

\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|}
\hline Item & a & b & c & d & e & f & g & h & i & j \\
\hline Weight & 30 & 50 & 20 & 10 & 120 & 100 & 90 & 90 & 40 & 10 \\
\hline Profit & 70 & 95 & 30 & 30 & 260 & 190 & 180 & 170 & 50 & 40 \\
\hline
\end{tabular}

Comments

in gate they give 4 or 5 elements so hit and trial works for it.

---

Please put total question

otherwise it cannot be solved

---

Give the Capacity Of Knapsack?

---

@pradeepchaudhary @srestha mam

edited.

Answer 1

First of all you have to find profit by weight ratio and then according to ratio you have put this in tabular form

 according to weight= 10+10+30+120+20

then profit according to weight is= 40+30+70+260+30 = 430

 Answer is 430

Comments

This is dynamic one and in fractional knapsack 200 complete weight is useful but in this Weight of capacity 10 left behind.

---

@Rahul271996 how u did it? hit and trial? tabular method?plz see my Question note and ans accordingly.

---

This process is similar to that fractional knapsack but in this, you have to take either full or not means that you can not take fraction part you have to left it.