냅색 (1) 썸네일형 리스트형 [TIL] knapsack 알고리즘 (배낭 문제) knapsack problem - 배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값은 정해져 있고 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 넣을 짐을 고르는 방법을 찾는 문제 냅색 알고리즘은 물건 분할 유무에 따라 분할 가능한 문제와 0-1 문제로 나뉜다. 여기서 다룰 문제는 0-1 냅색 알고리즘으로 백준 12865 문제를 풀다가 접하게 되었다. 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,0.. 이전 1 다음
