[12920] 평범한 배낭2(코드 + 풀이)

 

Dynamic Programming 에 관한 문제중 대표 문제인 배낭 문제의 업그레이드 버전 문제이다.

평범한배낭1 은 아래에서 풀 수 있다.

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

위문제와 본문제의 공통점은

1. 물건 마다 가치가 존재한다는점: 본문제에서는 가치 -> 만족도 로 변경되었다.

2. DP로 푼다는 점

 

다만 차이점은

1. 물건의 개수가 주어지지않고 종류가 주어진다는 점

2. 각 물건이 주어지는 개수가 다 다르고 개수만큼 사용할 수 있다는 점

3. 그러므로 K인 변수가 추가된다.

 

최초생각은 변수 k의 개수를 각각 하나의 물건으로 분리하고 풀면 되지 않을까 했다.

for(int i=1;i<= N;i++){
    int Value, Capacity, k = 0;
    Value= sc.nextInt();
    Capacity= sc.nextInt();
    k = sc.nextInt();

    for(int j=0;j<k;j++){
        v[tot] = Value;
        C[tot] = Capacity;
        tot++;
    }
}

최초 입력이 

2 3
2 7 1
1 9 3

이었을때 12865 번 처럼

4 3
2 7 
1 9
1 9
1 9

이렇게 바꾸어서 풀면 될 줄 알았다.

for(int i=1;i<=N;i++){
    w = sc.nextInt();
    c = sc.nextInt();
    k = sc.nextInt();

    for(int j=0;j<k;j++){
        weight[tot] = w;
        Capacity[tot] = c;
        tot++;
    }
}

그 결과

 

런타임 에러가 나왔다.

 

괜히 문제가 12865: 골드V -> 12920: 플레티넘 IV 로 바뀐게 아닐거라 생각하고 

좀더 축소시킬 수 있는 문제를 생각해보았다. 

애초에 문제분류가 DP로 나있기 때문에 알고리즘 자체에 다른 방법이 있다고는 생각하지 않았다. (그렇다면 제목도 달랐을 것이다.)

DP함수 수행시간(횟수) 를 감소시켜야 한다고 생각했다.

 

1. 애초에 입력받은대로 V C K 를 3차원 배열로 정의해서 K값을 감소시켜 보려는 생각을 했다.

=> 아니? 코드를 처음부터 다시짜야한다. 너무 복잡해졌다. 일단 패스하기로 했다.(미친짓)

 

2. 예를들어 1 9 3 이라는 input val을

 

1 9

2 18

 

로 바꾸어보기로 했다.

이게 무슨말이냐? 예를들어서 1 9 3 이라는 input 이 주어졌다고 하자.

1 9 3 이라는 input에서 나올수 있는 새로운 input의 조합은

 

1 9

2 18

3 27

 

의 서로다른 3개의 input 으로 생각할 수 있다.

그런데 이러면 배낭 문제 1과 달라진게 없다. 역시나 input의 개수는 같기 때문에 런타임 에러가 발생할 것이라 생각하였다.

이렇게 DP의 벽에 갇혀가던 도중에 다시 코드를 모두 지우고 재귀로 풀어보려는 시도를 했다(미친짓)

 

수시간 고민하다가 다시 생각한 내용은 자연수 분할 이었고

1 2 8 에서 나올수 있는 조합은

1 2

2 4

3 6

..

8 16 인데

 

8 = 4+4 형태로 나타낼 수 있다. 그러니까..?

1 2

2 4

3 6

4 8 

만 있으면 5 6 7 8 을 나타낼 수 있고, 3도 마찬가지였다 1 + 2 로 나타낼 수 있지 않은가.

그래서 내린 결론은 8인 경우에는 

1 2 4 의 조합만으로 모든 경우를 다 표현할 수 있다는거..? 엥 그럼 8은 1 + 2 + 4가 아니지 않나 -> 그래서 1을 하나 더 추가해줬다.

8 = 1 + 1 + 2 + 4 이다. 그럼 8의 경우에는

8 - 8/2(4) = 4

4 - 4/2(2)= 2

2 - 2/2(1) = 1

1 로 나타낼 수 있다.

 

11일 경우엔 어떻게 할까 ?

 

11 - 11/2(5) = 6

6 - 6/2(3) = 3

3 - 3/2(1) = 2

2 - 2/2(1) = 1

1

11 = 5+3+1+1+1

아무튼 이런식으로 하면 k의 개수를 최대 (log2(k))+1의 개수로 줄일 수 있다. 

트리에서 아래의 그림을 보면 이해하기 편할 것이다.

https://csacademy.com/app/graph_editor/

편향 이진트리의 구조라고 생각해도 될 것 같다. (자식노드 = 부모노드/2)

 

결론적으로 이걸 구현하는 코드를 만들어보자

 

k가 홀수일경우 1을 더해서 2로 나눈수를 뺏고,

k가 짝수일경우 그냥 2로 나눈수를 뺏다.

 

10 -> 5 -> 2 ->  1 -> 1

11 -> 6 -> 3 -> 1 -> 1

 

for(int i=1;i<=N;i++){
    w = sc.nextInt();
    c = sc.nextInt();
    k = sc.nextInt();

    weight[tot] = w;
    Capacity[tot] = c;
    tot++;

    while(k>1) {
        int a = 0;
        if(k%2==1){
            a = (k+1)/2;
            k = k-a;
        }
        else{
            a = k/2;
            k=k-a;
        }
        weight[tot] = w*a;
        Capacity[tot] = c*a;
        tot++;
    }
}

아래와 같이 바꾸어주었다. 이후 DP 실행

 

멋진나

 

 

전체코드는 아래에 있다.

import java.io.IOException;
import java.util.Scanner;

public class Nov_20 {
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);


        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] Capacity = new int[10001];
        int[] weight = new int[10001];
        int tot = 1;

        int w, c, k = 0;
        for(int i=1;i<=N;i++){
            w = sc.nextInt();
            c = sc.nextInt();
            k = sc.nextInt();

//            for(int j=0;j<k;j++){
//                weight[tot] = w;
//                Capacity[tot] = c;
//                tot++;
//            }

            weight[tot] = w;
            Capacity[tot] = c;
            tot++;

            while(k>1) {
                int a = 0;
                if(k%2==1){
                    a = (k+1)/2;
                    k = k-a;
                }
                else{
                    a = k/2;
                    k=k-a;
                }
                weight[tot] = w*a;
                Capacity[tot] = c*a;
                tot++;
            }
        }

        N = tot;

        DP(Capacity,weight,N,M);
    }
    public static void DP(int[] C, int[] V, int N, int M){
        int [][]DP = new int[N+1][M+1]; //가치와 무게에 대한 2차원 배열(표), 최초의 DP[0][0] 은 0이다.

        for (int i = 1; i <= N; i++) {      //물건접근

            for (int j = 1; j <= M; j++) {  //무게접근
                if (V[i] > j)               //i번째 물건의 무게가 j보다 크면
                    DP[i][j] = DP[i - 1][j];//표에서 왼쪽물건 대입
                else                        //그렇지 않을경우
                    DP[i][j] = Math.max(DP[i - 1][j], DP[i - 1][j - V[i]] + C[i]);
                    //DP[i-1][j]와, DP[i-1][j-V[i]] + C[i] 비교
                    //즉 원래 존재했던 물건(왼쪽에 존재했던 물건)과
                    //원래 존재했던 물건(최초면 0이겠지?) +
            }
        }
        System.out.println(DP[N][M]);
    }
}