[백준] 12865 | 평범한 배낭 | C++
풀이의 출처: https://chanhuiseok.github.io/posts/improve-6/ 이 문제는 냅색 알고리즘(knapsack algorithm)이 무엇인지 알 수 있게 해주는 문제이다. 풀이의 핵심은 2가지로 나눠서 볼 수 있다. 1. 이차원 다이나믹 테이블 풀이 준비물이 있다. i번째 물건의 무게를 저장하는 배열 W, i번째 물건의 가치를 저장하는 배열 V, i번째 물건까지 고려할 때 j용량까지 담을수 있는 최대가치값 dp[][] dp[i][j]의 의미는 i번째 물건까지 고려할 때, j용량에 담을 수 있는 가치값의 최대합이다. 따라서 다음과 같이 2중 for문을 작성하려 한다. 1번째 물건부터 n번째 물건까지 i반복: 1용량부터 k용량까지 j반복: j번째 용량에 i물건 투입가능: dp[i..
2022.08.17