[JAVA] 백준 12920 - 평범한 배낭 2

문제

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

12920번: 평범한 배낭 2

해결 방법

• 평범한 배낭 문제 푸는 방법을 안다고 가정 ( 평범한 배낭 문제 풀이 => https://chb2005.tistory.com/158 )
• 평범한 배낭 문제와 유사하지만 물건들의 갯수가 1개 고정이 아닌 최대 10000개 까지 있을 수 있음
• 따라서 다른 해결책이 필요함
• 만약 물건1(무게:1, 가치:1)의 개수가 15개라고 가정해보자
• 처음 생각했던 방식은 물건1을 15개 복사해서 넣어주고 knapsack 알고리즘을 구현하는 방식이었음
• 이 방식을 사용하면 knapsack과 일치하기 때문에 정답은 구할 수 있음
• 하지만 knapsack의 시간 복잡도가 O(nm)이기 때문에 개수만큼 복사를 한다면
  • n이 100 * 1만 (100만)이 되고 m이 1만이기 때문에 시간초과 + 메모리초과가 발생할 것임
• 이를 해결하기 위해서 복사하는 개수를 최소한으로 정해야 함
  • 15 = 1 + 2 + 4 + 8** 임을 이용해보자
  1. 물건1 (무게:1, 가치:1)
  2. 물건1-2 (무게:1*2 = 2, 가치:1*2 = 2)
  3. 물건1-3 (무게:1*4 = 4, 가치:1*4 = 4)
  4. 물건1-4 (무게:1*8 = 8, 가치:1*8 = 8)
  • 이처럼 4번만 추가한다면?
• 물건1, 1-2, 1-3, 1-4를 이용해 물건1이 1~15번 사용되는 모든 경우의 수를 구할 수 있음
• 물건2가 13개라면 => 13 = 1 + 2 + 4 + 6
• 물건3이 17개라면 => 17 = 1 + 2 + 4 + 8 + 2
• 이 처럼 2의 제곱수만큼 곱한 값들을 넣어주고 마지막에 남는 수를 곱한 값을 넣어주고 knapsack 알고리즘을 적용한다면 제한 시간내에 문제를 해결 할 수 있음
• 시간복잡도 : O(n *m * log k) = O(100 * 10000 * log(10000) ) < 1초

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class p12920 {
    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 m = Integer.parseInt(st.nextToken());

        ArrayList<Thing> things = new ArrayList<>();
        things.add(new Thing(0, 0));        // index를 1부터 하기 위해 null값 하나 추가
        for(int i = 0 ; i < n ; i ++ ) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());   // 물건의 무게
            int c = Integer.parseInt(st.nextToken());   // 물건의 가치
            int k = Integer.parseInt(st.nextToken());   // 물건의 개수

            int tempK = 1;
            while(tempK <= k) {
                things.add(new Thing(tempK * v, tempK * c));
                k -= tempK;
                tempK *= 2;
            }
            if(k != 0) {
                things.add(new Thing(k * v, k * c));
            }
        }

        int[][] dp = new int[things.size() + 1][m + 1];
        for(int i = 1 ; i < things.size() ; i ++) {
            for(int j = 1 ; j <= m ; j ++) {
                if(j < things.get(i).weight) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - things.get(i).weight] + things.get(i).value);
                }
            }
        }

        System.out.println(dp[things.size() - 1][m]);
    }

    static class Thing {
        int weight, value;

        public Thing(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }
}