배낭 문제 (1) 썸네일형 리스트형 [백준 12865][C++] 평범한 배낭 문제 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 풀이 과정 이 문제는 다이나믹 프로그래밍하면 가장 대표적인 가방에 무게와 가치가 있는 물건을 최대 가치가 되도록 담는 문제이다. 다이나믹 프로그래밍의 핵심이라고 한다면 이전의 계산을 통해 중복되는 계산을 피하는 것에 있다. 이는 분할 정복과 느낌이 비슷하다. N개의 입력에 의해 발생할 수 있는 가짓수는 2^N 가지이다. DP는.. 이전 1 다음
