배낭 문제 (1) 썸네일형 리스트형 [Python] 백준 12865번 문제, 평범한 배낭 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, K까지의 최적값들을 계산해 최종 N, K일 때 최고의 가치가 몇 일지를 구해야 한다. 따라서 DP의 크기는 [N+1][K+1]이다. ([넣을 수 있는 물품 수][배낭 최대 무게 한도]) 배낭 문제 알고리즘에 대한 DP 연산식은 다음과 같다. (.. 이전 1 다음
