1.0Camdemy1.0http://media.usc.edu.twBranch-and-Bound 0/1 Knapsackhttp://media.usc.edu.tw/user/http://media.usc.edu.tw/sysdata/doc/c/c01d7fb12e705531/thumb_l.jpg360640<iframe width='720' height='405' id='ccShare3059' frameborder='0' src='http://media.usc.edu.tw/media/e/3059' allowfullscreen></iframe>video72040538:550/1 KnapsackProblem01All approaches for 0/1 Knapsack Problem:02Brute-Force Search or Exhaustive Search: 2n03The 0/1 Knapsack Problem04e.g. n = 6, M = 34A feasible solution: X1 = 1, X2 = 1, X3 = 0, X4 = 0, X5 = 0, X6 = 0-(P1+P2) = -16 (upper bound)Any solution higher than -16 cannot be an optimal solution.05Relax the Restriction06Upper Bound and Lower Bound07Relax the Restriction08e.g. n = 6, M = 34A feasible solution: X1 = 1, X2 = 1, X3 = 0, X4 = 0, X5 = 0, X6 = 0-(P1+P2) = -16 (upper bound)Any solution higher than -16 cannot be an optimal solution.09Relax the Restriction010Upper Bound and Lower Bound011e.g. n = 6, M = 34A feasible solution: X1 = 1, X2 = 1, X3 = 0, X4 = 0, X5 = 0, X6 = 0-(P1+P2) = -16 (upper bound)Any solution higher than -16 cannot be an optimal solution.012Expand the node with the best lower bound.013fs1280x720720x4041280x720http://media.usc.edu.tw/sysdata/doc/c/c01d7fb12e705531/thumb.jpghttp://media.usc.edu.tw/sysdata/doc/c/c01d7fb12e705531/cover.jpghttp://media.usc.edu.tw/sysdata/doc/c/c01d7fb12e705531/video/thumbs/storyboard.jpghttp://media.usc.edu.tw/sysdata/doc/c/c01d7fb12e7055311