냅색 알고리즘

문제출저 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 문제풀이 배낭 문제, 냅색 알고리즘 문제로 조합 최적화를 찾아야 한다. 허용치 k인 배낭에 무게 w의 물건들을 담아서 물건들의 가치 v가 가장 높은 경우를 구해야한다. 문제를 해결하기 위해 2차원 int 배열인 dp를 활용한다. 2차원 배열인 dp의 가로줄은 배낭의 무게, 세로줄은 아이템을 배치한다. 1 2 3 4 5 6 ..