backtracking2 10. Backtracking ㅣ Knapsack 문제 Backtracking ? 기존에 알아보았던 Divide＆conquer, Dynamic programming 그리고 나중에 알아볼 Greedy 등의 알고리즘은 문제를 효율적으로 풀기 위해 사용했지만, Backtracking은 효율성보단 정확성에 조금 더 초점에 둔 알고리즘이다. Knapsack 문제 ? 여러 물건의 무게와 가격이 주어지고, 배낭에 담을 수 있는 총 용량(크기 또는 무게) 제한 K가 있다면, 배낭 용량 제한 K를 넘지않도록 물건을 골라 배낭에 담는 문제 ☆ 목표 ❗ :선택한 물건의 가격(이익)의 합이 최대가 되도록 선택 Knapsack 문제의 여러가지 버전 1. fractional knapsack 문제 선택한 물건의 일부분을 배낭에 넣을 수 있는 문제. 가루처럼, 물건을 나눠 담을 수 있다.. 2021. 8. 18. 9. Backtracking ㅣ Subset sum 문제 Backtracking ? 기존에 알아보았던 Divide＆conquer, Dynamic programming 그리고 나중에 알아볼 Greedy 등의 알고리즘은 문제를 효율적으로 풀기 위해 사용했지만, Backtracking은 효율성보단 정확성에 조금 더 초점에 둔 알고리즘이다. Backtracking은 해를 찾는 도중 해가 아니어서 막히면, 이전으로 되돌아가서 다시 해를 찾아가는 기법인데, 미로찾기 예제를 들어서 조금 더 자세히 설명해보겠다. ㆍn x n 미로를 나타내는 이차원배열 M 설정. ㆍM[i][j] = 1 이면 길이고, 0이면 장애물이라고 가정. ㆍ오로지 길로만 가야하며, 아래쪽과 오른쪽에 이웃한 길로만 갈 수 있다고 가정. ㆍM[0][0]에서 출발해 M[n-1][n-1]로 도착해야 탈출 성공!.. 2021. 8. 12. 이전 1 다음
