BOJ_12865_평범한 배낭

1. 구분: 다이나믹 프로그래밍, 배낭 문제 언어: Java 전략 0-1 knapsack문제를 이용하여 문제를 해결한다. 물건을 차례대로 고려한다(포함하거나 포함하지 않거나) - 배낭 무게 내에서 물건을 포함할지 말지 고르고, 또한 그 가치를 포함/비포함 중 더 큰 것을 선택한다. 방법이 2가지가 있다 1, 2차원 배열을 활용하여 문제를 해결 - d[i][j]: i번째 물건을 고려할 때, 가방의 무게가 j일때 최대 가치 - i 번 물건을 고려(꼭 포함해야 하는게 아니다) - i-1번에서 현재 물건 포함한 상황과, i-1번째에서 포함하지 않은 상황 중 더 큰 것을 선택한다. 2. 1차원 배열을 활용하여 문제를 해결 - d[j]: 가방 무게가 j일때 최대 가치 - 가방의 무게가 가장 최대일 때 부터 현재 가..

2021.09.27