728x90 반응형 배낭문제1 배낭 문제 배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제이다. 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이 때 짐을 쪼갤 수 있다면 분할가능 배낭문제, 쪼갤 수 없다면 0-1 배낭문제 라고 한다. 0-1 배낭 문제 무게 제한이 50인 배낭에 다음과 같은 세 개의 물건을 넣는 문제이다. 넣은 물건들의 가치(v) 합이 최대가 되면 된다. 직관적으로 2,3번 물건을 넣어서 무게는 50에 맞추고, 가치를 220으로 하면 최적이다. zeroOneKnapsack(item, cap){ for i 2019. 4. 28. 이전 1 다음 728x90 반응형