[JAVA] 백준 12865 평범한 배낭

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

12865번: 평범한 배낭

 

- 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 

- 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다.

- 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다.

- 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 찾는 프로그램

 

 

문제 풀이 

 

배낭 문제(Knapsack)

 

- n개의 물건과 각 물건 i의 무게 wi와 가치 vi가 주어지고, 배냥의 용량이 C일 떄, 배낭에 담을 수 있는 물건의 최대가치를 찾는 문제 

- 배낭에 담은 물건의 무게의 합이 C를 초과하지 말아야 하고, 각 물건은 1개씩만 있다.

- 이러한 배낭 문제를 0-1 배낭 문제라고 하는데, 이는 각 물건이 배낭에 담기지 않은 경우 '0', 담긴 경우는'1'로 여기기 때문이다.

 

- 배낭 문제의 부분문제의 정의를 위해 물건은 하나씩 차례로 고려하면 되지만, 물건의 무게가 각각 다를 수 있기 때문에, 무게에 대해서는 배낭의 용량이 0(kg)으로 1(kg)씩 증가하여 입력으로 주어진 용량인 C(kg)이 될 때까지 변화시켜 가며 물건을 배낭에 담는 것이 가치가 더 커지는지 결정해야 한다.

 

- 배낭 용량은 C(kg)이지만, 배냥 용량이 0(kg)부터 1(kg)씩 증가할 경우의 용량을 '임시' 배낭 용량이라고 부르자.

- 따라서 배낭 문제의 부분문제를 다음과 같이 정의할 수 있다. 

 

K[i,w] = 물건 1~i까지만 고려하고, (임시) 배낭 용량이 w일때의 최대 가치

 

- 그러므로 문제의 최적해는 K[n,C] 이다.

 

입력 : 배낭의 용량 C, n개의 물건과 각 물건 i의 무게 wi와 가치 vi, 단 i=1,2,3,...,n
출력 : K[n,C]

for i=0 to n  K[i,0]=0 //배낭의 용량이 0일 떄
for w=0 to C k[0,w]=0 //물건 0이란 어떤 물건도 배낭에 담기 위해 고려하지 않았을 때 

for i=1 to n
{
	for w=1 to C { //w는 배낭의 (임시)용량이고, 마지막에는 w==C가 되어 배낭의 용량이 된다 
    	if(wi>w) //물건 i의 무게가 임시 배낭의 용량을 초과하면
        	K[i,w] = K[i-1, w]
        else //물건 i를 배낭에 담지 않을 경우와 담을 경우를 고려 
        	K[i,w] = max{K[i-1,w], K[i-1,w-wi]+vi}
     }
}

return K[n,C]

 

- 현재 배낭에 담아보려고 고려하는 물건 i의 무게 wi가 (임시)배낭의 용량 w보다 크면 물건 i를 배낭에 담을 수 없으므로, 물건 i까지 고려했을떄의 최대 가치 K[i,w]는 물건 (i-1)까지 고려했을 떄의 최대 가치 K[i-1,w]가 된다.

if(wi > w)
	K[i,w] = K[i-1,w]

 

- 만일 현재 고려하는 물건 i의 무게 wi가 현재 배낭의 용량 w보다 작거나 같으면, 물건 i를 배낭에 담을 수 있다. 그러나 현재 상태에서 물건 i를 추가로 배낭에 담으면 배낭의 무게가 (w+wi)로 늘어난다.

- 따라서 현재 배낭의 용량인 w를 초과하게 되어, 물건 i를 추가로 담을 수 없다.

 

- 물건 i를 배낭에 담기 위해서는 2가지 경우를 살펴보아야 한다. 

   1) 물건 i를 배낭에 담지 않는 경우, K[i,w] = K[i-1,w]가 된다. 

   2) 물건 i를 배낭에 담는 경우, 현재 무게인 w에서 물건 i의 무게인 wi를 뺀 상테에서 물건을 (i-1)까지 고려했을 때의 최대 가치인 K[i-1,w-wi]와 물건 i의 가치 vi의 합이 K[i,w]가 되는 것이다. 

else
	K[i,w] = max{K[i-1,w], K[i-1, w-wi] +vi}

 

 

 

정답 

 

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

public class Main {
    static int memo[][];
    static int W[];
    static int V[];
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); //물품의 수
        int k = Integer.parseInt(st.nextToken()); //무게
        
        V = new int[n+1]; //가치
        W = new int[n+1]; //무게
        
        memo = new int[n+1][k+1];
       
        
        for(int i=1; i<=n; i++)
        {
          st = new StringTokenizer(br.readLine());
          W[i] = Integer.parseInt(st.nextToken());
          V[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=k; j++)
            {
                if(W[i]>j)
                {
                    memo[i][j] = memo[i-1][j];
                }
                else
                {
                    memo[i][j] = Math.max(memo[i-1][j], memo[i-1][j-W[i]]+V[i]);
                }
            }
        }
        bw.write(memo[n][k]+"");
        
        bw.flush();
        bw.close();
    }
}