Branch-and-Bound 0/1 Knapsack | 實踐大學影音平台

實踐大學影音平台

Branch-and-Bound 0/1 Knapsack

38:55,
520 views,
2021-05-26,
上傳者: 系統管理者,
收藏 0

<< Prev Next >>
auto next
播放設定
寫筆記

1. 0/1 KnapsackProblem
2. All approaches for 0/1 Knapsack Problem:
3. Brute-Force Search or Exhaustive Search: 2n
4. The 0/1 Knapsack Problem
5. e.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.
6. Relax the Restriction
7. Upper Bound and Lower Bound
8. Relax the Restriction
9. e.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.
10. Relax the Restriction
11. Upper Bound and Lower Bound
12. e.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.
13. Expand the node with the best lower bound.

1. Algorithms
1.1

Algorithm_ch1
2. Time Complexity
2.1

Algorithm_ch2
3. Insertion Sort
3.1

Straight Insertion Sort
3.2

Insertion Table
3.3

The average Case of Insertion
4. Selection
4.1

Algorithm_selection_1
4.2

Algorithm_selection_2
5. Binary Search
5.1

Binary Search
5.2

Binary Search 2
5.3

Binary Search 3
6. Spanningtree
6.1

Algorithm_spanningtree
7. Prim
7.1

Algorithm_prim
8. 2 Way Merge
8.1

Algorithm_2waymerge
9. Huffman
9.1

Algorithm_huffman
10. Divide and conquer
10.1

Algorithm_divideandconquer
10.2

Divide and Conquer-Convex Hull Part-1
11. 2D max finding
11.1

Algorithm_2dmaxfinding
12. Closest pair
12.1

Algorithm_closestpair
13. Tree Searching
13.1

Algorithm_TreeSearching
13.2

Algorithm_TreeSearching_2
14. Prune and Search
14.1

Prune and Search Part-1
14.2

Prune and Search Part-2
14.3

Prune and Search Exercise
15. Branch and Bound
15.1

Branch-and-Bound 0/1 Knapsack
15.2

Algorithm_BranchandBound
15.3

A* Algorithm for the Shortest Path Problem
16. Personnel Assignment
16.1

Algorithm_PersonnelAssignment
17. Traveling Salesperson
17.1

Branch-and-Bound TSP Part-1
17.2

Branch-and-Bound TSP Part-2
17.3

Algorithm_QuickSort_1
17.4

Algorithm_QuickSort_2Pivot
17.5

Algorithm_TravelingSalesperson
17.6

慈濟-PaGamO-競賽之盾
17.7

慈濟線上競賽之盾
17.8

慈濟20210829線上競賽之盾
17.9

慈濟線上競賽之盾-新增班級及預建GoogleMeet
17.10

alg0505
17.11

alg0526
17.12

alg0609_bb_1
17.13

alg0609_bb_2

Prev Prune and Search Exercise

Next

Algorithm_BranchandBound

訪客如要回應，請先登入

資料夾 :

發表時間 :

2021-05-26 14:58:27

觀看數 :

520

長度 :

38:55

發表人 :

系統管理者

部門 :

www

QR Code :