A question, in 8:20 i dont understand why i have the same thing and it doesnt print in the new order. items = [('avocado',2.2,170),('pomelo',8,1500),('durian',22,1500),('cucumelon',0.26,15),('lyche',0.4,20),('star apple',1,200)] def greedy_fruit(items,capacity): items = sorted(items,key=lambda item:items[1],reverse=True) print(items) greedy_fruit(items,2000)
Hi Juan, Your code is almost the same only In the lambda function you should write item:item[1] so we want the second value from the tuple item stored in the list items. Hope this clarifies the issue good luck and thanks for your question.
Hi Sophie, Thank you for your kind words. You are correct at the time, I was unaware of the floor division operator but it definitely makes the solution more elegant.
Hi fay rooz, Glad you liked the video! The dynamic solution I showed was an example of a bottom up/tabulation method, I did not really state this clearly. You could ofcourse also use a recursive solution which would then call itself and increase the weight of the bag.
@@cstosti5161 Thanks, makes sense. To work out the collection of items that gave the optimal value, I saved the j-index of the item that gives the max bag value, for each bag value. I then back-tracked the optimal path. Is there a better method?
Awesome, As far as I am aware backtracking is the only way to retrieve the optimal allocation of items when we use dynamic programming. I personally cannot think of another way.
Nice explanation, how do you suppose you can adapt this when one fruit can have multiple weights and profits associated with it? And the constraint being you can only choose at max only one fruit type?
Thank you, I am glad you liked the video. The extension where a fruit has multiple weights and a different profit is very interesting. I would say that the optimization problem becomes a bit more complex. If we assume that each fruit has a certain weight distribution and we assume profit to be a function of this weight. Then we could try to maximize the expected profit. The constraint of only selecting one fruit type makes the problem easier since the number of solutions in the feasible would be equal to the number of fruit types.
Hi there JDjd nDndn, I hope I spelled your username correctly. The items are visible in the table at the beginning of the video. They are basically a selection of fruits
Hi Pritam, Thank you for your comment. I would love to make more video's on dp, but work & uni are taking all of my time. I hope that in the future I will be able to start producing on a weekly basis again.
Hi BaBa aBBa thanks for your question. I have never used BFS to solve this type of problem before so I will have to do some research. Let me know if you have solved it!
Sure, the way to think about this is like asking the question: when will I have more value if I include the items in the backpack. Or if I do not include them. If we do not include them we still have bag[i]. But if we do include them then we will have the value of the best combination at bag[i-weight] plus the value of the new products we added in. Hope this clarifies the line. The max operator just takes the best scenario.
There is a Problem with the code which is that it takes repeating values from 1-D arrays for summing problems when i try to find best combination , it uses the best pair as many times as it can to extract the best over-value when it should exhaust/use every value only once , maybe this program isnt for that so if you could help with this particular problem it'll be really helpfull
Hi Arpit, Yes you are correct the problem you are referring to is known as a binary knapsack problem. In which products can only be bought once. There is a very nice article on the website geekforgeeks with several implementations of a 0/1 knapsack problem. Good luck and thanks for your comment!
13:06 could you have done num_of_fruit = (capacity // weight )
Hi Vastauine,
Indeed integer division would also have been an option there. It makes the code more concise.
A question, in 8:20 i dont understand why i have the same thing and it doesnt print in the new order.
items = [('avocado',2.2,170),('pomelo',8,1500),('durian',22,1500),('cucumelon',0.26,15),('lyche',0.4,20),('star apple',1,200)]
def greedy_fruit(items,capacity):
items = sorted(items,key=lambda item:items[1],reverse=True)
print(items)
greedy_fruit(items,2000)
Hi Juan,
Your code is almost the same only In the lambda function you should write item:item[1] so we want the second value from the tuple item stored in the list items. Hope this clarifies the issue good luck and thanks for your question.
Fantastic explanation. Just a minor suggestion, in the greedy method, num_of_fruit can be simply calculated by using capacity//weight
Hi Sophie, Thank you for your kind words. You are correct at the time, I was unaware of the floor division operator but it definitely makes the solution more elegant.
Great explanation! Thank you.
How is the dynamic solution recursive?
Hi fay rooz,
Glad you liked the video! The dynamic solution I showed was an example of a bottom up/tabulation method, I did not really state this clearly. You could ofcourse also use a recursive solution which would then call itself and increase the weight of the bag.
@@cstosti5161 Thanks, makes sense. To work out the collection of items that gave the optimal value, I saved the j-index of the item that gives the max bag value, for each bag value. I then back-tracked the optimal path. Is there a better method?
Awesome, As far as I am aware backtracking is the only way to retrieve the optimal allocation of items when we use dynamic programming. I personally cannot think of another way.
good explanation style. You will rock bro
Salaam Ussama,
Thanks for your kind words. Happy that you enjoyed the video.
Nice explanation, how do you suppose you can adapt this when one fruit can have multiple weights and profits associated with it? And the constraint being you can only choose at max only one fruit type?
Thank you, I am glad you liked the video. The extension where a fruit has multiple weights and a different profit is very interesting. I would say that the optimization problem becomes a bit more complex. If we assume that each fruit has a certain weight distribution and we assume profit to be a function of this weight. Then we could try to maximize the expected profit. The constraint of only selecting one fruit type makes the problem easier since the number of solutions in the feasible would be equal to the number of fruit types.
Hello! Would you be willing to help me solve a similar problem I am facing? If so, is there some way I can contact you?
where can you see the items you have used?
Hi there JDjd nDndn,
I hope I spelled your username correctly. The items are visible in the table at the beginning of the video. They are basically a selection of fruits
Bro can u upload a video on dynamic programming basics to advanced in python. Can't find anyone teachin dp in python?👍
Hi Pritam, Thank you for your comment. I would love to make more video's on dp, but work & uni are taking all of my time. I hope that in the future I will be able to start producing on a weekly basis again.
th-cam.com/video/oBt53YbR9Kk/w-d-xo.html there you go
my pycharm didn't run the code i dont know why
Hi Ceren,
Not sure what is the cause of the issue. Maybe try running the code in a jupyter notebook or online python interpreter.
please can you explain how to solve the issue with breadth-first search
if you have a link just leave a comment thanks in advance
Hi BaBa aBBa thanks for your question. I have never used BFS to solve this type of problem before so I will have to do some research. Let me know if you have solved it!
@@cstosti5161
thanks for your reply, no not yet I would be grateful if you explain to us the algorithm
I would love to but sadly I am currently very busy with university so I have little time to produce video’s 😢 But I will put it on my cool ideas list.
Can you please explain the line of bag[i] = max(bag[i], bag[i-weight]+value), I was confused about this row.
Sure, the way to think about this is like asking the question: when will I have more value if I include the items in the backpack. Or if I do not include them. If we do not include them we still have bag[i]. But if we do include them then we will have the value of the best combination at bag[i-weight] plus the value of the new products we added in. Hope this clarifies the line. The max operator just takes the best scenario.
There is a Problem with the code which is that it takes repeating values from 1-D arrays for summing problems when i try to find best combination , it uses the best pair as many times as it can to extract the best over-value when it should exhaust/use every value only once , maybe this program isnt for that so if you could help with this particular problem it'll be really helpfull
Hi Arpit,
Yes you are correct the problem you are referring to is known as a binary knapsack problem. In which products can only be bought once. There is a very nice article on the website geekforgeeks with several implementations of a 0/1 knapsack problem. Good luck and thanks for your comment!
🦍very🦍good🦍video🦍broski🦍!🦍
Thank you kingkelpo for your kind comments