[백준] 평범한 배낭 12865번 (java) 냅색 1차원으로 풀이

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

 

풀이 방법,

이번 문제는 0-1 배낭 문제(0-1 Knapsack Problem)로, 1차원 DP를 활용하여 최적의 해결법을 찾는다.

DP 배열을 사용하여 주어진 무게 제한 내에서 최대 가치를 찾는 방식으로 풀이하였다.

 

1. DP 배열 정의

• dp[j] → 무게 j일 때 배낭에 담을 수 있는 최대 가치를 저장

• 초기값은 0으로 설정

2. 각 물건을 순회하며 DP 테이블 갱신

• 현재 물건을 넣을 수 있는 최대 무게부터 역순으로 탐색 (이전 값이 유지되도록)

• 현재 가방을 선택하는 경우 vs. 선택하지 않는 경우를 비교하여 dp 갱신

 

dp[j] = max(dp[j], dp[j - weight] + value)

 

import java.io.*;
import java.util.*;

public class P_12865 {

    static int n, k;
    static int[] dp = new int[100001];
    static public class BackPack{
        int weight, value;
        BackPack(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }
    static ArrayList<BackPack> backPacks = new ArrayList<>();


    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 배낭의 수
        k = Integer.parseInt(st.nextToken()); // 제한 무개
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            backPacks.add(new BackPack(Integer.parseInt(st. nextToken()), Integer.parseInt(st.nextToken())));
        }
        for (int i = 0;i < backPacks.size();i++){
            for (int j = k;j >= backPacks.get(i).weight;j--) {
                dp[j] = Math.max(dp[j], dp[j - backPacks.get(i).weight] + backPacks.get(i).value);
            }
        }
        System.out.println(dp[k]);
    }
}