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 ?
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga.
Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus.
Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
In 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
Do 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) ?
hmm..... 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 sub-problems 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.
Not the answer you are looking for? Search for more explanations.
There 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 sub-problem that must be solved at every node.
I 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 ?
seems 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