백준 12865번 - 평범한 배낭(Node.js)

백준 12865번 - 평범한 배낭(Node.js)

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

 

 

---

첫 번째 나의 풀이

• 제출시 결과는 틀렸습니다.
• 간단하게 이 코드에 대해 설명하자면, 이중 for문을 사용하여 모든 가치 or 가치의 합의 최댓값의 경우의 수를 worthArr이라는 배열에 넣어주고, worthArr의 값 중 최댓값을 답으로 설정하여 풀었다.
• 하지만, 이 방법에는 생각해보니 많은 오류가 있었다.
• 이중 for문을 사용했기 때문에, 최대 2개의 가치의 합만 계산하기 때문이다. 물론 문제의 입력 예제에는 2개의 가치의 합까지만 고려하도록 나와있지만, 입력의 수가 많고 고려해야할 가치의 갯수가 3개 이상이라면, 이 방법으로는 당연히 풀 수 없다.

 

 

---

두 번째 나의 풀이

• 제가 두 번째의 방법을 알았을 때는 처음에 이해가 가지 않아, 이해하는데 상당한 시간이 걸렸습니다..
• 이 문제는 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)라는 동적 프로그래밍 방법을 사용해야 풀 수 있습니다.
• 물건을 쪼갤 수 없는 배낭문제(0/1 Knapsack Problem)을 잘 모르시는 분들이라면, 아래의 링크를 클릭해서 이해하셔야 아래 코드를 이해할 수 있을 것 같습니다. 😂😂😂 

2022.07.27 - [Algorithm] - 물건을 쪼갤 수 없는 배낭 문제(0/1 Knapsack Problem)

물건을 쪼갤 수 없는 배낭 문제(0/1 Knapsack Problem)