[Algorithm/BOJ] KnapSack _ DP

knapsack problem : 배낭 문제 용량이 m인 가방이 하나 주어졌을 때, 각각 가치와 무게가 정해진 n개의 물건들에 대하여 합이 m 이하이고 가치의 합이 최대가 될 수 있는 물건 부분집합을 구하는 문제이다. 배낭문제는 fractional knapsack or 0-1 knapsack 두가지가 있다. 후자는 물건을 쪼갤 수 없다고 가정하는 알고리즘으로, 지금 다루어 볼 것이다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(..

2022.10.13