4 Replies - 996 Views - Last Post: 16 June 2016 - 01:54 PM

#1 somecoder  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 04-March 16

binary knapsack problem

Posted 15 June 2016 - 02:25 AM

Hi, so i've got trouble with this part of the problem

How do i construct a graph after finding and calculating the optimal path in a binary knapsack problem?

I've attached a picture of the graph, can someone please explain how do i draw such a graph, in a
step by step way.

I figured out there are 10 leaves cause of 10 permutations

If we have ABCD then we can place 4 letters in first position 3 in second 2 in third and 1 in fourth

Not sure if that is correct either, i'd be happy if someone can help me with this


Thanks!

Attached image(s)

  • Attached Image

This post has been edited by somecoder: 15 June 2016 - 02:26 AM


Is This A Good Question/Topic? 0
  • +

Replies To: binary knapsack problem

#2 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: binary knapsack problem

Posted 16 June 2016 - 06:11 AM

Quote

I figured out there are 10 leaves cause of 10 permutations

If we have ABCD then we can place 4 letters in first position 3 in second 2 in third and 1 in fourth


Nope. You are correct that the number of leaves is the number of combinations, but permutations are useless here. Permutations are different arrangements of the same elements. In a knapsack ABCD is the same as DCBA. To represent combinations you use a 4 digit binary number where each digit represents whether or not a particular element is included. ABC is represented as 1110 and BCD is 0111. There are 2^4=16 combinations.

You've got the right idea with your graph but it is incomplete. The idea is that if you trace from the root to all leaves then you will cover every combination. Your graph covers some combinations such as 1010, but what about 0011? Just add more nodes to cover all combinations. Once you have all the leaves, you scan them and select the biggest number that fits the constraint as your solution.
Was This Post Helpful? 2
  • +
  • -

#3 somecoder  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 04-March 16

Re: binary knapsack problem

Posted 16 June 2016 - 10:15 AM

Hey, thanks for reply i appreciate it, however i got this as a solution, this drawn graph was already given as a solution.

So i just want to know how would i go about drawing such a graph what i have to look for and
how to start!

thanks!
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12189
  • View blog
  • Posts: 45,251
  • Joined: 27-December 08

Re: binary knapsack problem

Posted 16 June 2016 - 10:17 AM

It's really a dynamic programming problem. You pick an item, then recurse for the remaining weight and rest of the items. The graph is just a visualization of this recursive algorithm. So if you focus on understanding this basic procedure, the graph should come naturally.
Was This Post Helpful? 0
  • +
  • -

#5 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: binary knapsack problem

Posted 16 June 2016 - 01:54 PM

Ahh, so you are trying to visually represent the execution of an algorithm. Basically, each level represents one of the elements. Going left means you include the element and going right means you exclude it. You go left as far as you can, then backtrack and go right adding the total along the way. The green dots means that from the root to that node is less than the constraint. A red dot means that adding the element will cause you to exceed the constraint, thus there is no reason to continue and you need to stop and backtrack. I'm not certain, but i believe the blue nodes indicate that there is no way from that point to surpass a previously discovered solution thus there is no reason to continue from there.

In the problem, A=55, B=25, C=50, and I'm assuming D=35. The constraint appears to be around 110.

The algorithm starts by going left A (which means include A), left B, and left C. A+B+C=130 which exceeds our constraint so we backtrack one step and go right C. At this point, we go left D which exceeds the constraint so we back track and go right D. We are at a leaf and under our constraint so for the moment we store 80 as a potential solution. However, we need to check other paths for a better one so we backtrack and check the unexplored paths. We eventually discover a better one that adds up to 105 and that remains our best solution as we check the remaining paths meaning that AC is the best combination. It is worth noting for example that when we try excluding A and B, then the most we can have is 85 from C and D which is why we don't continue to check that path and instead mark it with a blue terminating dot. We already have a better solution that gives us 105. I hope this helps you understand a bit better.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1