[Algorithm Champions] Week 4, No.4

문제

---

풀이

• capacity를 넘지 않으면서 더한 값은 최대일 때의 무게와 index를 찾는 문제이다.

• dp table을 만들면서 최대 무게를 찾는다.
  - [curVal, curWeight], cap

  1. 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)
     
     
  2. curWeight가 cap보다 클 때
     2.1. 이전 item과 현재(첫 번째) cap의 값 가져오기
     [beforeVal, beforeWeight] & 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;
    }
}