[냅색 알고리즘]최대 점수 구하기/평범한 배낭 문제

문제

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를얻을 수 있도록 해야 합니다.(해당 문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있다)

---

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

12865번: 평범한 배낭

해당 문제와 백준 12865번 평범한 배낭 문제는 동일한 문제 풀이로 진행되기 때문에 같이 포스팅해둔다.

 

문제풀이

https://choi95.tistory.com/137

[냅색 알고리즘]동전교환

전체적인 문제 풀이는 이전 포스팅의 동전교환 문제와 유사하다.

하지만 최대 점수와 평범한 배낭 문제는 아래와 같은 차이점이 있다.

• 동전교환 문제는 사용되는 동전종류가 중복되어 사용하는 것이 가능
• 최대 점수와 평범한 배낭 문제는 동일한 문제를 풀거나 같은 물건을 담을 수 없음

각 limit에 대응해 이뤄질 수 있는 value를 구하기 위해 동전교환 문제와 같이 앞에서부터 순회하며 점화식을 통해 계산하게 되면 동일한

문제를 계속 풀게되거나 같은 물건을 계속 담게 되는 상황이 발생하기 때문에 가장 마지막 인덱스에서부터 역순으로 순회가 이뤄져야 된다.

 

코드_최대 점수 구하기

function solution(m, arr) {
  let answer = 0;
  let dy = Array.from({length: m + 1}, () => 0);
  
  for(let i = 0; i < arr.length; i++) {
    let ps = arr[i][0];
    let pt = arr[i][1];
    for(let j = m; j >= pt; j--)  {
      dy[j] = Math.max(dy[j], dy[j - pt] + ps);
    }
  }
  answer = dy[m];
  return answer;
}

let arr = [[10, 5], [25, 12], [15, 8], [6, 3], [7, 4]];
console.log(solution(20, arr));

 

코드_평범한 배낭

function solution(m, arr) {
  let answer = 0;
  let dy = Array.from({length: m + 1}, () => 0);
  
  for(let i = 0; i < arr.length; i++) {
    let weight = arr[i][0];
    let value = arr[i][1];
    for(let j = m; j >= weight; j--)  {
      dy[j] = Math.max(dy[j], dy[j - weight] + value);
    }
  }
  answer = dy[m];
  return answer;
}

let arr = [[6, 13], [4, 8], [3, 6], [5, 12]];
console.log(solution(7, arr));