YYYEJI

0-1 knapsac 문제는 제한된 가방 용량(W) 안에서 물건들의 가치(bi)와 무게(wi)가 주어졌을 때, 물건들을 조합해 최대의 가치를 가지도록 하는 문제입니다. 단, 각 물건은 딱 한 번만 사용할 수 있습니다. 배낭문제,수도코드(pseudo code)를 살펴보겠습니다. for w = 0 to W B[0, w] = 0 for i = 1 to n B[i, 0] = 0 for w = 1 to W if wi B[i-1, w] B[i,w] = bi + B[i-1, w-wi] else B[i,w] = B[i-1, w] else B[i, w] = B[i-1, w] 해당 코드는 냅색(Napsack) 문제를 동적 계획법(Dynamic Programming)으로 푸는 방법 중 하나인 0/1 냅색 문제를 푸는 코드입..

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