A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 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 ?

  • This Question is Closed
  1. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  2. maitre_kaio
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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) ?

  3. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  4. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  5. maitre_kaio
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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 ?

  6. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  7. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.