wonseok.log wonseok.log

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 이 문제를 그리디라고 오해하여 중량 대비 가치가 가장 큰 경우를 넣는다고 할 경우 예외가 발생하게 됩니다. 그리디가 아닌 DP로 해결해야 하면 DP로 유명한 0-1 knapsack 알고리즘입니다. D[i][w] : 현재 w 무게가 남은 상태에서 i번째 item선택까지 최대 가치 if w[i] < w, D[i][w] = max(D[i-1][w-w[i]]+v[i], D[i-1][w]) : i번째 Item을 담을 수 있다면, i-1번째까지 Item을 담으면서 현재 담을 수 있는 무게가 w-w[i]만큼 남은 경웅의 최대 가치합에 i번째 Item의 가치를 합한 값과 D[i-1][w] 값 비교 else, D[i][w] = D[i-1][w] #include #..