배낭 알고리즘이라고도 한다. 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 베낭에 넣을 때, 가치의 합이 최대가 되도록 고르는 알고리즘이다.
가방에 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보다 작을 때
dp[i][j] = dp[i-1][j]
j가 현재 물건의 무게 w와 같거나 클 때
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가 저장된다.
뒤에서부터 저장되어오게 만들었다.
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 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));
개선 방식으로 코드를 짜서 정답을 맞췄다.