[ 백준 / 12865번 ] Gold V : 평범한 배낭 - solve by Java

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

 

해설 

 

이 문제는 knapsack 알고리즘으로 푸는 문제이다. 

 

냅색 알고리즘은 무게를 0~K까지 계산하면서 가장 가치가 높으면서 가방에 넣을 수 있는 것들을 차례대로 입력하는 방식이다. 

2차원 배열로 풀었지만 1차원 배열이 더 이해하기 쉽다고 생각한다. 

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

public class 평범한배낭 {
	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[] nap = new int[K+1];// 1차원
		for(int i =1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			for(int k = K;k>=w; k-- ) {
				if (nap[k-w]+v >nap[k]) {
					nap[k] = nap[k-w]+v;
				}
			}
		}
		System.out.println(nap[K]);
	}
}

af 

무게 배열인 nap이 있다. 

nap의 크기는 K로 0~K 까지의 값을 가지고 있다. ( 크기는 K+1)

여기에 이제 들어오는 V:value와 W : weight를 비교 해가면서 이 nap배열을 업데이트 하는 방식이 냅색이다. 

점화식처럼 차근 차근 변화시켜나간다고 생각하면 된다. 

19번 줄 이후가 알고리즘인데, 

들어오는 N개의 값을 모두 비교해 주기위해 처음 for(int i= 1; i< N;)을 이용하였고, 

그리고 메인은 들어온 N을 무게가 K인 값에 저장할 수 있는 가? 이다

1. K 가방 무게 최대치 부터 ~ w 까지 ( w가 가방에 들어갈 수 있는 최소이므로. 

여기에서 먼저 들어갈 수 있는지를 조건문으로 파악해서 돌리게 된다 

여기서 중요한 점이 K부터 시작해서 점차 줄여가는 방식으로 되어 있는 점인데, 밑에서 부터 올라오게 되면, 

예를 들어 K 가 8이고 현재 물건의 무게 w가 4인 경우 w가 4일때의 무게와 비교해서 nap[8]을 업데이트 하기 때문이다. 

그럼 v+v가 nap[8[이 되므로, 뒤(K)에서 부터 w까지 해 주어야 중복되지 않으면서 k-w가 0미만이 되지 않는다. 

이제 이 값을 비교해 주는데, 

nap[k-w]+v ( 현재 들어있는 거에서 w가 들어가고, 난 다음의 가치 nap[k-w] : w의 무게가 빠졌을 경우 최선의 가치 

nap[k] : w를 넣지 않았을 때 최선의 가치를 비교해서 

현재 물건을 가방에 넣는 것이 더 가치가 커지면 그 값을 넣게 된다. nap[k] = nap[k-w]+v;

 

그럼 결국 최종 마지막 N까지 계산한 이후에 K가 가방 크기가 K일 떄 최선이 된다.