Baekjoon12865: 평범한 배낭

평범한 배낭

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

46452

17466

11410

35.908%

문제

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

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

준서가 여행에 필요하다고 생각하는 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)가 주어진다.

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

출력

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

 

풀이1

Top-Bottom으로 푼다고 할 때 초항을 생각한다. 위 문제에서 5 12가 초항이 된다.

N	K
5	12
3	6
4	8
6	13

1) 초항을 선택한 경우

→ 가방에는 7-5=2의 무게를 더 담을 수 있다. K는 12가 누적된다. 다음항들을 찾아보지만 물건을 더 추가할 수 없다

2) 초항을 선택하지 않은 경우

→ 가방 공간은 아직 7이 있고 2항 (3, 6)을 선택한다면 7-3=4의 공간이 남고 6이 누적된다

→ 2항을 선택한 상태에서 3항을 선택할 수 있고 누적은 14가 된다. 더 이상 물건을 추가할 수 없게 된다

3) 1항과 2항을 선택하지 않은 경우

→ 3항을 선택하거나 4항을 선택한다. 이 중 최대값은 13이므로 13을 선택한다

 

식 세우기

1항을 기준으로 식을 세워본다. 1항을 선택될 수도, 되지 않을 수도 있다. 하지만 둘 상황에 따라서 배낭에 남은 무게가 달라진다.

dp[N][K] = Math.max( dp[N-1][K] , dp[N-1], [K-현재물건이 차지하는 무게]

같은 i항이지만 이전의 물건들을 선택했는지 안했는지에 따라서 남은 무게가 다를 수 있다. 즉 i항의 K값은 여러 개가 될 수 있다.

 

제한 조건

물건 가치의 최대합은 100,000 x 1000 = 100,000,000 으로 int범위지만

무게의 최대합은  100,000 x 100,000 = 10,000,000,000 으로 int범위를 벗어난다. 즉 dp는 int배열을 사용할 수 없다.

물건배열 크기에 주의해야한다. 최대 100,000까지 가능하므로 [N][100001]로 설정해주어야 연산할 수 있다

아래 코드에서는 편의상 [N+1][K+1]로 설정했다

 

Top-Bottom

import java.io.*;
import java.util.StringTokenizer;
public class Main {
	static Double dp[][];
	static int[][] thing;
	static Double knapsack(int N, int K) {
		if(N<=0 || K<0)return dp[0][0]; //K<=0이 아님을 주의한다 K=0일 때 0이상의 값을 가질 수 있다
		else if(dp[N][K]==null) {
			if(K>=thing[N][0]) { //K보다 현재 물건의 무게가 클 경우 연산할 수 없도록 한다
			dp[N][K] = Math.max(knapsack(N-1,K), knapsack(N-1,K-thing[N][0])+thing[N][1]);
			}else{
				dp[N][K] = knapsack(N-1,K);
			}
			}
		return dp[N][K];
	}
	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());
		thing = new int[N+1][2]; //0에는 무게, 1에는 가치
		dp = new Double[N+1][K+1];
		dp[0][0]=0.0;
		
        for(int i=1;i<N+1;i++){
			st = new StringTokenizer(br.readLine()," ");
			thing[i][0]=Integer.parseInt(st.nextToken());
			thing[i][1]=Integer.parseInt(st.nextToken());
		} //배열에 입력값을 집어넣는다
	
		System.out.println(String.format("%.0f", knapsack(N,K)));
	}
}

 

풀이2

모든 항의 무게에 따라서 경우가 달라질 수 있지만, 이것을 하나의 배열 안에 최대값을 갱신하는 방식으로 만들어본다.

dp[K+1] 이라는 배열 안에서 배열의 index는 현재 더 담을 수 있는 물건의 무게를 뜻하며 10항은 10만큼 무게를 더 담을 수 있다는 뜻이다. 현재 물건의 무게가 3일 때, 모든 항에 대해서 index를 3을 빼주고 그에 해당하는 물건의 가치를 더해준다.

dp[ 현재항 물건의 무게 ] = Math.max( dp[ 현재항 보다 큰 모든 항 - W ] + 현재 물건의 가치, dp[ 현재항 물건의 무게 ] )

모든 무게(K)에 대한 최대값(V)에서 현재 입력된 물건의 무게(W)만큼 index를 빼주고 가치를 더해 최대값을 갱신한다

 

Bottom-Top

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
        int K = sc.nextInt();
        int dp[] = new int[K+1]; //무게에 따라 최대값만 갱신한다
        
		while(N-- > 0) {
			int Weight = sc.nextInt();
            int Value = sc.nextInt();
            
			for(int i=K; i>=Weight; i--) //모든 i에 대해 무게를 빼주고 가치를 더한값을 갱신해준다
				dp[i-Weight] = Math.max(dp[i] + Value, dp[i-Weight]);
		}
		System.out.println(dp[0]); // K=0, 무게를 다 썼을 때 최대값이 나온다
	}
}