12865번

    백준 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 다이나믹 프로그래밍의 기본 유형이라고 할 수 있는 문제이지만, 2차원 리스트를 이용한 메모이제이션을 생각하는 과정과 사소한 실수로 푸는데 시간이 많이 소요됐다. 문제를 요약하면 N개의 물건은 각각 무게와 가치를 갖고 있는데, 주어진 배낭의 용량(K)을 넘지 않게 물건을 넣어서 배낭 안에 들어있는 물건들의 가치의 합을 최대로 만드는 ..