(백준) 평범한 베낭 - 12865

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

12865번: 평범한 배낭

 

🐢문제설명

베낭에 최대한의 이익을 내면서 담는 것이 목표인 문제인데, 이러한 유형을 냅색 문제라고 한다. 냅색 문제는 대부분 dp로 풀면 되는경우가 많다. 이번 문제 또한 대표적인 냅색 문제이므로 dp로 풀어보자.

 

🐢풀이법

먼저 베낭에 담을 수 있는 최대 무게만큼 배열을 선언해 준다. 그러면 배열의 각 인덱스는 베낭에 담긴 무게가 되고, 해당 인덱스가 갖는 값은 그 때 가질 수 있는 최대 가치가 될 수 있다.

 

따라서, 가방의 최대 크기부터 현재 물건을 자신의 가방에 넣을 수 있는 무게의 하한선 까지 모든 무게에 대해서 확인을 해줘야 한다.

-> 현재 가방의 무게에서 가지는 가치 vs (현재 가방의 무게 - 물건의 무게)에서 가지는 가치 + 물건의 가치

 위 비교를 통해서 가방이 각 무게마다 가질 수 있는 최대 가치를 갱신 해주면 된다.

 

🐢코드

import java.util.*;
import java.io.*;
 
public class Main {
    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()); // N개의 물건
        int W = Integer.parseInt(st.nextToken()); // 가방의 최대 허용 무게
 
        int[] dp = new int[W + 1]; // 모든 무게에서 가치를 측정하기 위한 배열
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
 
            for (int weight = W; weight >= w ; weight--) { // 가방의 남는 공간을 최대부터 최소로 돌면서 비교
                dp[weight] = Math.max(dp[weight], dp[weight - w] + p); // 넣지 않는 경우 vs 넣는 경우
                // 참고로 역순으로 돌아야 중복을 막을 수 있다
            }
        }
        System.out.println(dp[W]);
    }
}