목록Knacsack (1)

YYYEJI

[Algorithm] 배낭문제 DP로 풀기

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 냅색 문제를 푸는 코드입..
Algorithm 2023. 4. 19. 00:01
이전 Prev 1 Next 다음