2011-12-27

Branch-and-Bound with the 0-1 Knapsack problem(Best-First Search)(0-1 배낭 문제-최고우선탐색)

In general, the breadth-first search strategy has no advantage over a depth-first search (backtracking). However, we can improve our search by using our bound to do more than just determine whether a

AlgorithmsBranch and Bound

2011-12-27

Branch-and-Bound with the 0-1 Knapsack problem(Breadth-First Search)(0-1 배낭 문제-너비우선탐색)

We show how to use the branch-and-bound design strategy by applying it to the 0-1 Knapsack problem. First we discuss a simple version called breadth-first search with branch-and-bound pruning. After t

AlgorithmsBacktracking

2011-12-24

Backtracking with the 0-1 Knapsack problem(Depth-First Search)(0-1 배낭 문제-깊이우선탐색)

Recall that in this problem we have a set of items, each of which has a weight and a profit. The weights and profits are positive integers. A thief plans to carry off stolen items in a knapsack, and t

Blog Powered by Hexo

Tag: 0-1 배낭 문제

Branch-and-Bound with the 0-1 Knapsack problem(Best-First Search)(0-1 배낭 문제-최고우선탐색)

Branch-and-Bound with the 0-1 Knapsack problem(Breadth-First Search)(0-1 배낭 문제-너비우선탐색)

Backtracking with the 0-1 Knapsack problem(Depth-First Search)(0-1 배낭 문제-깊이우선탐색)