A community for students.
Here's the question you clicked on:
 0 viewing
maitre_kaio
 4 years ago
In lectures 13 and 14, there's a representation of the solution to the knapsack problem using a decision tree.
I see why the problem has an optimal substructure, but I don't get why there are overlapping subproblems. I don't see , by looking at the decision tree, why the same things are computed over and over. Could someone explain that ?
maitre_kaio
 4 years ago
In lectures 13 and 14, there's a representation of the solution to the knapsack problem using a decision tree. I see why the problem has an optimal substructure, but I don't get why there are overlapping subproblems. I don't see , by looking at the decision tree, why the same things are computed over and over. Could someone explain that ?

This Question is Closed

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0In lecture John gives an example of code which the only things that change are the available weight (aWeight) and which values you're getting from the lists (i).It means that the knapsack has a value of available weight (aWeight) and you are choosing to take or not the item i of the list. The thing is, you can have a certain aWeight at a certain i decision with different previous choices. p.s.: I’m not American so forgive my possible English mistakes

maitre_kaio
 4 years ago
Best ResponseYou've already chosen the best response.0Do you mean that you're seeing that the subproblems are averlapping by looking at the code, but that you can't see it by looking at the decision tree (maybe it's too small) ?

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0hmm..... you have the option to take or not take something. you make that decision everywhere in the tree. the decisions to take or not take are the subproblems and they overlap because they are made on the same nodes of the tree  the paths that they traverse on the tree overlap. anyway, i made that up so .... still not sure i could identify a problem that would benefit from dp.

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0There is no visual overlap on the diagram, the overlap is conceptual. At every node you are trying to make the same decision, how to optimize the value of the items in your knapsack subject to the constraint of item weight. You have two possible choices, take, or don't take the current item. To find out the optimal solution for the current node, you need to know the optimal solution for the two nodes below. Finding the optimal solution for any given node is the overlapping subproblem that must be solved at every node.

maitre_kaio
 4 years ago
Best ResponseYou've already chosen the best response.0I agree that there is an optimal substructure, and it can be seen by looking at the decision tree. But that does not imply that the subproblems overlap. These are two different concepts. But the argument of bwCA makes sense. But then it would imply that all problems that can be resolved using decision trees have also this characteristic. Do you agree ? And is this the case ?

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0seems like that would be the case, optimizing a problem that can be represented as a decision tree would benefit from dP one thing they are trying to get us to understand is that if you can categorize a problem as a certain class of problem then you can use solutions/algorithms that have been found successful in the past for that class. hope that made sense
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.