[Algorithm Champions] Week 4, No.4
문제
풀이
-
capacity를 넘지 않으면서 더한 값은 최대일 때의 무게와 index를 찾는 문제이다.
-
dp table을 만들면서 최대 무게를 찾는다.
- [curVal, curWeight], cap- curWeight가 cap보다 작거나 같을 때
1.1 cap에서 curWeight를 뺀다.
-> cap -= curWeight (두 번째 cap)
1.2. 이전 item과 cap(위에서 curWeight한 것)일 때의 값을 가져와 curVal과 더한다.
-> [beforeVal, beforeWeight] & (두 번째 cap) 일 때의 값 + curVal
1.3. 더한 curVal과 이전 item & 첫 번째 cap일 때의 값과 비교하여 큰 값을 저장한다.
-> Math.max(additionVal, beforeAdditionVal)
- curWeight가 cap보다 클 때
2.1. 이전 item과 현재(첫 번째) cap의 값 가져오기
[beforeVal, beforeWeight] & cap
- curWeight가 cap보다 작거나 같을 때
-
dp table을 맨 끝 셀부터 시작하여 맨 처음 item까지 돌면서 이 최대값을 구했을 때 사용된 item의 index를 찾는다. (백트래킹)
1. 맨 마지막 셀과 바로 위의 셀의 값을 비교한다.
-> 만약 두 값이 같다면 현재 셀을 사용하지 않은 것이다. 두 값이 다르다면 현재 셀을 사용한 것이다.
2. 이를 이용하여 두 값이 다를 경우 현재 item의 index값을 리스트에 넣는다.
3. 만들어진 리스트를 reverse하여 반환한다.
DP Table
초기 table
[x,y] & cap | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
[] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
[1,2] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
[4,3] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
[5,6] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
[6,7] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
[x,y] & cap | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
[] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
[1,2] | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
[4,3] | |||||||||||
[5,6] | |||||||||||
[6,7] |
이런 식으로 끝 줄까지 채워나간다.
최종 테이블
[x,y] & cap | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
[] | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
[1,2] | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
[4,3] | 0 | 0 | 1 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 5 |
[5,6] | 0 | 0 | 1 | 4 | 4 | 5 | 5 | 5 | 6 | 9 | 9 |
[6,7] | 0 | 0 | 1 | 4 | 4 | 5 | 5 | 6 | 6 | 9 | 10 |
코드
package com.company.w4;
import java.util.ArrayList;
import java.util.Arrays;
/*
date: 21.07.11
[curVal, curWeight], cap
< MaxVal 찾기 >
1. curWeight가 cap보다 작거나 같을 때
-> cap에서 curWeight를 뺀다.
cap - curWeight
-> 이전 [,]와 cap이 (cap - curWeight)한 값일 때 값을 가져와서 curVal과 더한다.
[beforeVal, beforeWeight] & (cap - curWeight) 일 때 값 + curVal
-> 더한 curVal과 이전 [,]와 현재 cap일 때의 값과 비교하여 큰 값을 저장한다.
Math.max(additionVal, beforeAdditionVal)
2. curWeight가 cap보다 클 때
-> 이전 [,]와 현재 cap의 값 가져오기
[beforeVal, beforeWeight] & cap
< index list 찾기 >
1. 맨 마지막 셀과 바로 위의 셀의 값을 비교한다.
maxValTable[maxValTable.length-1][maxValTable[0].length-1]
& maxValTable[maxValTable.length-2][maxValTable[0].length-1]
1.1. 비교한 값이 같다면 현재 값을 사용하지 않았다.
-> 바로 위 셀로 이동
maxValTable[maxValTable.length-2][maxValTable[0].length-1]
1.2. 비교한 값이 다르다면 변화가 생겼다는 뜻! -> 현재 셀을 사용했다.
-> cap - curWeight [10,[1,3]] 10-7 = 3
-> maxValue - curVal 10-6 = 4 (필요없다!)
-> 현재 인덱스를 최종 인덱스 리스트에 추가하기.
-> 바로 위 줄의 변경된 캡(cap - curWeight)일 때의 셀 이동
2. 반복
3. 최종 인덱스 리스트가 나오면 그 리스트를 뒤집어주어 반환.
<결과>
초기 dp table
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Final dp table
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 1, 4, 4, 5, 5, 5, 5, 5, 5]
[0, 0, 1, 4, 4, 5, 5, 5, 6, 9, 9]
[0, 0, 1, 4, 4, 5, 5, 6, 6, 9, 10]
maxVal = 10
answer.maxValue = 10
answer.indexs = [1, 3]
*/
public class No4_2 {
static class Value {
int maxValue;
int[] indexs;
Value(int maxValue, int[] indexs) {
this.indexs = indexs;
this.maxValue = maxValue;
}
}
public static void main(String[] args) {
int[][] items = {{1, 2}, {4, 3}, {5, 6}, {6, 7}};
int capacity = 10;
Value answer = knapsack(items, capacity);
System.out.println("answer.maxValue = " + answer.maxValue);
System.out.println("answer.indexs = " + Arrays.toString(answer.indexs));
}
public static Value knapsack(int[][] items, int capacity) {
Value result = new Value();
int[][] maxValTable = new int[items.length + 1][capacity + 1];
ArrayList<Integer> indexList = new ArrayList<>();
for (int i = 1; i < maxValTable.length; i++) {
int curValue = items[i - 1][0];
int curWeight = items[i - 1][1];
for (int j = 1; j < maxValTable[0].length; j++) {
if (curWeight <= j) {
int diffWeight = j - curWeight;
int addVal = maxValTable[i - 1][diffWeight] + curValue;
maxValTable[i][j] = Math.max(addVal, maxValTable[i - 1][j]);
} else if (curWeight > j) {
maxValTable[i][j] = maxValTable[i - 1][j];
}
}
}
int finalMaxVal = maxValTable[maxValTable.length - 1][maxValTable[0].length - 1];
result.maxValue = finalMaxVal;
// 백트래킹, 인덱스 구하기
int curCap = maxValTable[0].length - 1;
for (int i = maxValTable.length - 1; i > 0; i--) {
int curVal = maxValTable[i][curCap];
if (curVal == maxValTable[i - 1][curCap]) {
continue;
} else {
indexList.add(i - 1);
curCap -= items[i - 1][1];
}
}
int[] reverseIdx = new int[indexList.size()];
int arrIdx = indexList.size() - 1;
for (int idx : indexList) {
reverseIdx[arrIdx--] = idx;
}
result.indexs = reverseIdx;
return result;
}
}
Author And Source
이 문제에 관하여([Algorithm Champions] Week 4, No.4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ffwang/Algorithm-Champions-Week-4-No.4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)