knapsack

DP - Knapsack (배낭문제)

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 🕹️ Knapsack 알고리즘 과정 DP 문제 중 하나로, 배낭의 크기 k와 n개의 물건의 무게(w)와 가치(v)가 주어졌을 때, 가방에 물건을 k에 넘지 않도록 넣고 최대 가치의 합을 구하는 문제이다. ex) 배낭의 크기는 k이고, 5개의 물건의 무게와 가치가 다음과 같이 주어졌을 때, 최대 가치의 합을 구하기 물건 1 : w =..