Basic ConceptRecall 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 the knapsack will break if the total weight of the items placed in it exceeds some positive integer $W$. The thief’s objective is to determine a set of items that maximizes the total pro..

Basic ConceptThe m-Coloring problem concerns finding all ways to color an undirected graph using at most m different colors, so that no two adjacent vertices are the same color. We usually call the m-Coloring problem a unique problem for each value of m. An important application of graph coloring is the coloring of maps. 👉 m-그래프 채색 문제는 비방향그래프에서 서로 인접한 정점이 같은 색을 갖지 않도록 최대 m개의 다른 색으로 칠하는 방법을 모두 찾..

Basic ConceptIn the Sum-of-Subsets problem, there are n positive integers (weights) $w_i$ and a positive integer W. The goal is to find all subsets of the integers that sum to W. As mentioned earlier, we usually state our problems so as to find all solutions. 👉 부분집합의 합을 구하는 문제는 n개의 양의 정수(무게) $w_i$와 양의 정수 $W$가 주어졌을 때, 합이 $W$가 되는 정수의 부분집합을 모두 찾는 것이다. n-Queens 문제처럼 모든 해답을 찾도록 알고리즘을 구현할 것이다. Exampl..

Basic ConceptThe classic example of the use of backtracking is in the n-Queens problem. The goal in this problem is to position n queens on an n×n chessboard so that no two queens threaten each other; that is, no two queens may be in the same row, column, or diagonal. The n-Queens problem is a generalization of its instance when n = 8, which is the instance using a standard chessboard. For the s..

Basic ConceptIf you were trying to find your way through the well-known maze of hedges by Hampton Court Palace in England, you would have no choice but to follow a hopeless path until you reached a dead end. When that happened, you’d go back to a fork and pursue another path. Think how much easier it would be if there were a sign, positioned a short way down a path, that told you that the path l..