알고리즘/동적 계획법(Dynamic Programming)
12865-백준-평범한 배낭
1. 문제 출처 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 2. 풀이 해당 문제는 흔히 Knapsack 알고리즘 문제이다 가방의 담을 수 있는 무게가 정해져 있을 때, 최대한 가치를 가지도록 배낭을 싸는 문제이다.. 이를 다음과 같이 정의할 수있다. 1.현재 배낭의 한계량 보다 큰 무게의 물건은 넣지 않는다. 2.현재 배낭의 한계량 보다 작은 무게라면 더 좋은 가치의 물건을..
