knapsack1 10. Backtracking ㅣ Knapsack 문제 Backtracking ? 기존에 알아보았던 Divide＆conquer, Dynamic programming 그리고 나중에 알아볼 Greedy 등의 알고리즘은 문제를 효율적으로 풀기 위해 사용했지만, Backtracking은 효율성보단 정확성에 조금 더 초점에 둔 알고리즘이다. Knapsack 문제 ? 여러 물건의 무게와 가격이 주어지고, 배낭에 담을 수 있는 총 용량(크기 또는 무게) 제한 K가 있다면, 배낭 용량 제한 K를 넘지않도록 물건을 골라 배낭에 담는 문제 ☆ 목표 ❗ :선택한 물건의 가격(이익)의 합이 최대가 되도록 선택 Knapsack 문제의 여러가지 버전 1. fractional knapsack 문제 선택한 물건의 일부분을 배낭에 넣을 수 있는 문제. 가루처럼, 물건을 나눠 담을 수 있다.. 2021. 8. 18. 이전 1 다음
