[백준] 12865번: 평범한 배낭 -JAVA

문제 바로가기 > 12865번: 평범한 배낭

 

전형적인 0/1 냅색 알고리즘으로, DP로 풀 수 있다.

 

1. 초기화

• 최대 무게 K를 수용할 수 있는 dp 배열을 선언하고, 크기를 K + 1로 설정하여 모든 인덱스를 0으로 초기화
• dp[j]는 무게 j일 때의 최대 가치를 저장

2. 동적 프로그래밍을 통한 최대 가치 계산

• 각 물건에 대해 반복을 수행, 물건의 무게를 weight, 가치를 value
• dp 배열을 역순으로 갱신: 이는 각 물건을 한 번만 고려하도록 하여 중복을 방지
• dp[j] (무게 j에서의 최대 가치)는 dp[j] (현재 가치)와 dp[j - weight] + value (현재 물건을 추가했을 때의 가치) 중 더 큰 값으로 갱신
• j는 K부터 weight까지 감소하면서 계산

3. 결과 출력

• dp[K]에 저장된 값, 즉 배낭의 최대 용량에서 담을 수 있는 최대 가치를 출력
• 이 값은 주어진 무게 제한 내에서 선택할 수 있는 물건들의 가치 합의 최대치

 

역순으로 처리하는 이유는 각 물건이 배낭에 한 번만 들어갈 수 있도록 보장하기 위해서이다. 만약 순방향으로 배열을 업데이트한다면, 한 번의 반복으로 물건이 여러 번 배낭에 들어갈 수 있는 문제가 발생할 수 있다.

EX)
배낭의 최대 용량이 10kg이고, 다음 두 가지 물건이 있다:
물건 A: 무게 3kg, 가치 50물건 B: 무게 4kg, 가치 60

1) 순방향으로 업데이트할 경우:
- dp[3]을 계산할 때, 물건 A를 넣어 가치 50을 기록
- dp[6]을 계산할 때 (A를 이미 고려한 상태에서), 물건 A를 다시 넣을 수 있게 되어, dp[3] + 50 = 100이 된다.
=> 이는 물건 A를 두 번 넣을 수 있다는 것을 의미

2) 역순으로 업데이트할 경우:
dp[10]부터 dp[3]까지 역순으로 계산하면서, dp[3], dp[6], dp[9] 등에서 물건 A를 고려할 때, 물건 A를 추가할 때마다 이전에 계산된 가치를 사용하지 않는다. 즉, 물건을 중복해서 넣지 않게 된다. 물건 B에 대해서도 마찬가지로 dp[10], dp[9], dp[8] 등을 업데이트하면서, 물건 B를 한 번만 계산에 포함한다.

 

 

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

public class _12865 {
    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 k = Integer.parseInt(st.nextToken());
        int[] dp = new int[k + 1];  // dp 배열의 크기를 k + 1로 설정

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            // j를 k부터 weight까지 역순으로 반복
            for (int j = k; j >= weight; j--) {
                dp[j] = Math.max(dp[j], value + dp[j - weight]);
            }
        }
        System.out.println(dp[k]);  // 최대 가치 출력
    }
}

 

 

1106번 호텔 문제도 0/1 냅색 알고리즘 문제인데 순차적으로 하는 이유는 이 문제와 달리 중복이 허용되기 때문이다 

“어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.