목록knapsack (1)

Rosie

[Algorithm] 배낭문제, 냅색(Knapsack)이란?

Knapsack이란? 냅색(Napsack) 문제는 배낭에 담을 수 있는 무게 한계가 정해져 있고, 각각의 물건들은 무게와 가치가 정해져 있을 때, 배낭에 담을 수 있는 최대 가치의 합을 구하는 문제입니다. 배낭문제는 대표적으로 두 가지 종류로 나뉩니다. 1. 0-1 knapsack problem: 각각의 물건은 단 하나씩만 존재하며, 배낭에 담거나 담지 않거나 둘 중 하나의 선택만 가능하다. 2. Fractional knapsack problem: 각각의 물건은 무게에 비례하여 일부분만 담을 수 있으며, 물건을 자를 수 있다. Branch and Bound Branch and Bound는 최적화 문제를 풀기 위한 알고리즘으로 가능한 모든 해를 차는 대신, 최적의 해를 빠르게 찾기 위해 탐색 범위를 줄이는..
Algorithm 2023. 4. 18. 22:32
이전 Prev 1 Next 다음