12865 평범한 배낭
1. 배낭 문제 알고리즘
배낭 문제 알고리즘을 이용해서 풀면 된다.
배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값이 정해져 있을 때,
일정한 가치, 무게가 정해져 있는 짐들을 배낭에 담아야 한다.
이 때 가치의 합이 최대가 되도록 짐을 고르는 방법
두 가지로 분류 할 수 있는데,
1) 물건을 쪼갤 수 있는 배낭 문제 => 가치가 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식
=> 그리디 알고리즘 사용
2) 물건을 쪼갤 수 없는 배낭 문제 => dp를 활용해서 해결
2. 문제 풀이
이 예제는 물건을 쪼갤 수 없는 배낭 문제로 dp를 활용한다.
문제 예제를 가지고 설명하겠다.
4 7
6 13
4 8
3 6
5 12
물품의 수(N) : 4
배낭에 넣을 수 있는 최대 무게(K) : 7
item 배열의 0열에는 각 물건의 무게, 1열에는 물건의 가치를 입력하겠다.
=>
물건 무게 물건 가치
item[1][0] = 6 item[1][1] = 13
item[2][0] = 4 item[2][1]= 8
item[3][0] = 3 item[3][1] = 6
item[4][0] = 5 item[4][1] = 12
그러면 dp 를 이용해서 풀이한다.
dp[i][j] = 0~i번째 물건 중 1개 이상 선택해서 그 무게 합이 j가 되었을 때
선택한 물건들로부터 얻는 최대 가치
즉, 예제에서
1번째 물건의 무게와 가치 : 6 13
2번째 물건의 무게와 가치 : 4 8
3번째 물건의 무게와 가치 : 3 6
4번째 물건의 무게와 가치 : 5 12
0번째 물건은 없기 때문에 얻을 수 있는 가치도 없다.
=> dp 배열의 0 행렬은 모두 0이다.
역시, 물건들을 선택해서 그 무게의 합이 0이 되게 만들 수 없으므로 얻을 수 있는 가치도 없다.
=> dp 배열의 0열은 모두 0이다.
1) 1행
그러면 이제 1행을 생각해보자.
dp[1][1] = 0~1번째 물건으로 1의 무게를 만들었을 때 얻을 수 있는 최대 가치
예제에서 주어진 물건의 무게는 6,4,3,5 이므로 1의 무게를 만들 수 없다.
따라서 그 가치도 0이다.
그러다가 dp[1][6] 이 되었을 때는
0~1번째 물건으로 6의 무게를 만들 수 있게 된다.
첫번째 물건의 무게가 6이며 그 가치가 13이다.
=> dp[1][6] = 13
dp[1][7] 은 0~1번째 물건으로 7의 무게를 만들어야 한다.
그러면 일단 첫번째 물건으로 6의 무게를 만든다.
그런 다음 1만큼의 무게가 남아 있는데, 위 표에서 보면 무게 1의 최대 가치는 0이다.
따라서 무게 6의 물건 가치 13에 무게 1의 물건 가치 0을 더해서 13 이 된다.
이때, dp[0][7] = 0 과 위의 13 값 중 더 큰 수, 즉 13이 dp[1][7] 이 된다.
이에 대한 설명은 아래에서 자세히 하겠다.
2) 2행
역시 3열까지는 dp 값이 0이다가,
4열이 되면,
dp[2][4] = 0~2 번째 물건 중 선택해서 무게 4를 만들었을 때 최대 가치
예제에서 첫번째 물건은 무게가 6이기 때문에 안되고,
두번째 물건은 무게가 4이다.
그리고 그 가치가 8이므로
dp[2][4] = 8
dp[2][5] 역시 8이다.
dp[2][6] = 0~2번째 물건 중 선택해서 무게 6을 만들었을 때 최대 가치인데
첫번째 물건의 무게가 6이고, 그 가치는 13이다.
두번째 물건의 무게는 4이고, 그 가치는 8이다.
그럼 이 문제에서 사용되는 dp 식을 자세히 설명하겠다.
i = 물건, j = 무게를 의미한다.
1. j 가 item[i][0] 보다 크거나 같을 경우
이 경우는 가방에 넣을 수 있는 무게가 j인데,
i번째 물건의 무게 (item[i][0]) 가 이보다 작거나 같아서,
j - (i번째 물건의 무게) 만큼 다른 물건으로 채워 넣는 경우이다.
=> dp[i][j] = Math.max(dp[i-1][j], item[i][1] + dp[i-1][j-item[i][0]])
2. j 가 item[i][0] 보다 작을 경우
이 경우는 가방에 넣을 수 있는 무게 (j) 보다
i번째 물건의 무게 (item[i][0]) 가 커서 i번째 물건을 넣지 못한다.
그래서 i-1번째의 dp값으로 i번째 dp값을 채워넣는 경우이다.
=> dp[i][j] = dp[i-1][j]
dp[2][6] 은 두가지 경우 중 첫번째에 해당한다.
그래서
dp[2][6] = Math.max(dp[1][6], item[2][1] + dp[1][2]) = Math.max( 13, 8+0) = 13
3. dp[2][6] = Math.max(dp[1][6], item[2][1] + dp[1][2]) 설명
1)
위의 식에서 dp[1][6] 이 어떻게 나왔을지 생각해보자.
일단 식 dp[2][6] 에서
0~2번째 물건 중 선택해서 무게 6을 만들어야 한다.
첫번째 물건의 무게와 가치 : 6 13
두번째 물건의 무게와 가치 : 4 8
이때 첫번째 물건의 무게가 6이므로 이를 사용하면 된다.
이 가치는 13이 된다.
그런데 이 가치는 dp[1][6]에서 구했다.
그렇기 때문에 dp[2][6]에서 이를 사용하는 것이다.
2)
item[2][1] + dp[1][2]
이 부분이 어떻게 나왔을지 생각해보자.
첫번째 물건 말고도 두번째 물건을 사용해서 무게 6을 만들 수 있다.
즉, 두번째 물건은 무게가 4이고, 그 가치는 8이다.
따라서 item[2][1] = 8 을 더하는 것이고
6-4=2 만큼의 무게를 더 채워야 한다.
그런데 위의 그림에서 무게 2의 가치는 0임을 알 수 있다.
그리고 그 값을 dp[1][2] 로 나타내었다.
그러면 dp[0][2], dp[2][2] 도 있는데 dp[1][2] 를 사용한 이유가 있을 것이다.
dp는 최대 가치를 찾고 있는 것이기 때문에, 무게 2의 가치도 최대값을 찾아야 한다.
그렇기 때문에 dp[0][2] 보다는 dp[1][2] 가 더 값이 크다.
왜냐하면 dp[0][2] 는 0번째 물건만 사용해서 2의 무게를 만들었을 때 최대 가치이고,
dp[1][2] 는 0~1번째 물건 중 선택해서 2의 무게를 만들었을 때 최대 가치이다.
즉 선택지가 더 많다. 그래서 그 값이 더 크다.
그러면 dp[2][2]가 dp[1][2]보다 더 클 가능성이 있다.
그런데, dp[2][2]는 0~2번째 물건 중 선택해서 2의 무게를 만들었을 때 최대가치인데,
item[2][1] + dp[1][2]
이 식에서 알 수 있듯이,
item[2][1] 에서 이미 2번째 물건을 사용했다.
따라서 2번째 물건 제외 0~1번째 물건 중 선택해서 2의 무게를 만들어야 하기 때문에
dp[1][2] 가 되는 것이다.
3) 3행, 4행
위에서 설명한 대로 채우면 된다.
4)
위에서 dp 식이 두가지 있었다.
그 중에서 첫번째 식은 설명했지만, 두번째는 설명하지 못했다.
그 부분을 살펴보겠다.
j 가 item[i][0] 보다 작을 경우
=> dp[i][j] = dp[i-1][j]
dp[4][3]을 살펴보자
j는 무게로, 3이다.
i는 물건으로 4이다.
item[4][0] = 5 라서
j < item[4][0] 이다.
즉 가방에 3무게 만큼 물건을 넣을 수 있는데,
i번째 물건의 무게는 5로 더 크다.
그래서 i번째 물건은 넣을 수 없다. 고려할 사항이 아니게 된다.
때문에 i-1번째 dp값, 즉 0~3번째 물건 중 선택해서 무게 3을 만든 경우로
i번째 dp값을 채우면 되는 것이다.
=> dp[4][3] = dp[3][3]
3. 최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int item[][] = new int[N+1][2];
for(int i=1; i<=N;i++) {
st = new StringTokenizer(br.readLine(), " ");
item[i][0] = Integer.parseInt(st.nextToken());
item[i][1] = Integer.parseInt(st.nextToken());
}
int dp[][] = new int[N+1][K+1];
for(int i = 1; i<=N; i++) {
for(int j=1; j<=K; j++) {
if(j>= item[i][0]) {
dp[i][j] = Math.max(dp[i-1][j], item[i][1] + dp[i-1][j-item[i][0]]);
}else {
dp[i][j] = dp[i-1][j];
}
}
}
System.out.println(dp[N][K]);
}
}
참고 블로그 :
[알고리즘] 배낭 문제(Knapsack Problem)
배낭 문제(Knapsack Problem) 배낭 문제란 배낭에 담을 수 있는 무게의 최대값이 정해져 있고, 일정한 가치와 무게가 정해져있는 짐들을 배낭에 닮을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법
dheldh77.tistory.com
https://fbtmdwhd33.tistory.com/60
[백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이)
-내 생각 이 문제의 경우 혼자 풀어보려고 해서 결과는 잘 나오는 것 같은데 어떤 반례에서 걸리는지 계속 오답처리를 받아서 결국 검색을 해봤는데, 이러한 무게와 가치가 함께 주어지는 문제
fbtmdwhd33.tistory.com