냅색(Knapsack) 알고리즘

bkboy·2022년 6월 22일

알고리즘

목록 보기

12/14

냅색(Knapsack) 알고리즘

배낭 알고리즘이라고도 한다. 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 베낭에 넣을 때, 가치의 합이 최대가 되도록 고르는 알고리즘이다.

예제

가방에 15kg까지 담을 수 있고, 세가지 물건이 있을 때 가치를 최대로 하려면 어떤 물건을 담아야하는가
A => 가치 : 10, 무게 : 13kg
B => 가치 : 6, 무게 : 6kg
c => 가치 : 5, 무게 : 6kg

이 문제는 그리디로 풀 수 없다. 가치를 최대로 선택을 하면 A를 담고 끝이나는데 정답은 A를 제외하고 B,C를 담는 것이기 때문이다.

미리 말하자면, 특정 물건을 담지 않았을 때가 최선의 선택임을 고려해주는 것이 냅색 알고리즘의 핵심이다.

동적 프로그래밍을 이용하면,

dp[i][j] = 처음부터 i번째까지 물건을 살펴보고, 배낭의 용량이 j였을 때 배낭에 들어간 물건의 가치합의 최대값

i번째 물건의 무게는 w[i]이고, 가치는 v[i]이다.
배낭에 물건이 들어가 무게가 추가가 되면 j - w[i]가 된다.

j가 현재 물건의 무게 w보다 작을 때
- 용량이 j인 배낭에 i번째 물건을 넣지 않는다.
- 현재 물건을 담지 않았으므로 이전의 값을 복사한다.
```
dp[i][j] = dp[i-1][j]
```
j가 현재 물건의 무게 w와 같거나 클 때
- 현재 물건을 담을 수 있다.
- 물건을 담는다면 배낭을 남은 용량이 줄어든다(빼준다).
- dp에 저장되는 건 가치임으로 더해준다.
- 물건을 담았을 때와 담지 않았을 때의 가치를 비교해준 뒤 더 큰 값을 할당해준다.
```
dp[i][j] = Math.max( dp[i-1][j] , dp[i-1][j-w[i]] + v[i])
```

말로 풀어서 설명하면 i번째 물건을 넣었을 때와 넣지 않았을 때, 둘 중 더 가치가 큰 것을 저장한다는 의미이다.

코드

const sol = (weight, value, m) => {
  const n = weight.length;
  const dp = Array.from(Array(n + 1), () => Array(m + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (weight[i] <= j) {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
      }
    }
  }

  return dp[n - 1][m - 1];
};

const weight = [13, 6, 6];
const value = [10, 6, 5];

console.log(sol(weight, value, 15)); // 11

개선하기

const sol = (weight, value, m) => {
  const n = weight.length;
  const dp = new Array(m + 1).fill(0); // index 무게일 때, 최대 value
  for (let i = 0; i < n; i++) {
    const [w, v] = [weight[i], value[i]];
    for (let j = m; j >= w; j--) {
      if (w <= j) {
        dp[j] = Math.max(dp[j], dp[j - w] + v);
      }
    }
  }

  return dp[m];
};

const weight = [13, 6, 6];
const value = [10, 6, 5];

console.log(sol(weight, value, 15)); // 11

dp를 일차원 배열로 수정했다.
index 무게일 때, 최대 value가 저장된다.

뒤에서부터 저장되어오게 만들었다.

백준 평범한 배낭 12865

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

제한 사항

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [n, m] = input.shift().split(" ").map(Number);
const table = input.map((e) => e.split(" ").map(Number));

const sol = (table, n, m) => {
  const dp = new Array(m + 1).fill(0); // index 무게일 때, 최대 value
  for (let i = 0; i < n; i++) {
    const [w, v] = [table[i][0], table[i][1]];
    for (let j = m; j >= w; j--) {
      if (w <= j) {
        dp[j] = Math.max(dp[j], dp[j - w] + v);
      }
    }
  }

  return dp[m];
};

console.log(sol(table, n, m));