[Java] 배낭 문제 (안녕)

진짜 평범한 배낭 문제 중에 한 문제다.

 

이 문제에서 N의 범위가 20으로 비교적 작은 범위로 제한되어 있어 ArrayList를 사용하지 않고 크기가 22인 배열을 사용해 문제를 풀 수 도 있었지만 그냥 가변배열을 사용하고 싶어서 ArrayList를 선택했다.

 

배낭 문제에서 [물품의 수 = 사람의 수] 로, [견딜 수 있는 무게 = 체력] 으로 변환하면 쉽게 풀 수 있다. 

 

2차원 배열 선언하는 게 갑자기 생각이 안 나서 헷갈렸다. 행과 열의 구분을 헷갈리지 않도록 확실하게 기억해야 할 필요가 있을 듯

 

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

1535번: 안녕

 

 

 

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); //물품의 수 (사람 수)
        int K = 99; //견딜 수 있는 무게 (체력)
        int[][] dp = new int[N+1][K+1]; //가로가 100 세로가 N+1

        ArrayList<Integer> weight = new ArrayList<>();
        ArrayList<Integer> value = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        weight.add(0); //dp 문제이기 때문에 인덱스 0을 0으로 초기화
        value.add(0);
        for (int i = 0; i < N; i++) {
            weight.add(Integer.parseInt(st.nextToken()));
            value.add(Integer.parseInt(st2.nextToken()));
        }
        
        for(int i=1; i<N+1; i++){
            for(int j=1; j<K+1; j++){
                if(j<weight.get(i)){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight.get(i)]+value.get(i));
                }
            }
        }
        System.out.print(dp[N][K]);
    }
}

 

 

배낭 문제 핵심 

•  j < weight : d[i][j] = d[i-1][j]
• else: d[i][j] = max( dp[i-1][j], d[i-1][ j-weight[i] ]+value[i] ) 

 

배낭 문제에 대해 기억이 나지 않는다면 아래 글을 다시 보자.

 

https://com-squadleader.tistory.com/47

배낭 (평범한 배낭 문제)

https://com-squadleader.tistory.com/46

배낭 문제 (Knapsack Problem)