백준 12865 평범한 배낭

12865번: 평범한 배낭

문제 풀이 방법:
배낭이 가질 수 있는 최대의 무게와, 각각의 아이템을 넣었는지, 넣지 않았는지를 기준으로 dp 배열을 만듭니다.
각 열(i)은 물건을, 각 행(j)은 가방으 ㅣ일부분의 무게라고 가정하고 표를 채워나갈 때, 현재 고려중인 물건을 넣을 수 있는 무게에 도달하면 해당 물건을 넣고 남는 공간의 최대 가치를 채우거나, 아니면 넣지 않고 이전에 넣을 수 있는 무게의 최댓값으로 표를 채워나가면 제일 오른쪽 아래 칸의 값이 채울 수 있는 최댓값이 됩니다. 

문제 코드 

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

public class Main {
    public int solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoToken = new StringTokenizer(reader.readLine());
        int itemCount = Integer.parseInt(infoToken.nextToken());
        int totalWeight = Integer.parseInt(infoToken.nextToken());

        int[][] dp = new int[itemCount + 1][totalWeight + 1];
        int[][] items = new int[itemCount + 1][];
        for (int i = 1; i < itemCount + 1; i++) {
            StringTokenizer itemToken = new StringTokenizer(reader.readLine());
            items[i] = new int[]{
                    Integer.parseInt(itemToken.nextToken()),
                    Integer.parseInt(itemToken.nextToken())
            };
        }

        for (int itemNumber = 1; itemNumber < itemCount + 1; itemNumber++) {
            int itemWeight = items[itemNumber][0];
            int itemValue = items[itemNumber][1];
            for (int currentWeight = 0; currentWeight < totalWeight + 1; currentWeight++) {
                // 지금 무게에서 물건을 첨부 못하면 이전에 첨부한게 최고 가치
                if (itemWeight > currentWeight)
                    dp[itemNumber][currentWeight] = dp[itemNumber - 1][currentWeight];
                // 추가할 수 있다면,
                // 지금 아이템 가치 + 넣은 뒤 남은 공간에 넣을 수 있는, 마지막 최고가치
                // vs
                // 이전 최고 가치
                else
                    dp[itemNumber][currentWeight] = Math.max(
                            itemValue + dp[itemNumber - 1][currentWeight - itemWeight],
                            dp[itemNumber - 1][currentWeight]
                    );

            }
        }

//        System.out.println(Arrays.deepToString(dp));

        return dp[itemCount][totalWeight];
    }

    public static void main(String[] args) throws IOException {
        System.out.println(new Main().solution());
    }
}