백준_12865 평범한 배낭(자바) / DP

시간 & 메모리 제한

문제

입력 & 출력 & 예제

DP를 이용한 문제풀이

package com.Back;

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

public class Back_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());
		
		bag[] b = new bag[K+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());
			b[i] = new bag(w, v);
		}
		
		int dp[][] = new int[N+1][K+1];
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= K; j++) {
				dp[i][j] = dp[i-1][j];
				if(j>=b[i].w) {
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-b[i].w]+b[i].v);
				}
			}
		}
		System.out.println(dp[N][K]);
	}
	
	static class bag{
		int w;
		int v;
		public bag(int w, int v) {
			super();
			this.w = w;
			this.v = v;
		}
		
	}
}

 

- 평범한 배낭의 문제의 경우에는 DP를 이용해서 문제풀이를 진행했습니다.

 

- bag라는 클래스를 만들어서 bag의 무게와 가치를 담는 배열을 만들었습니다.

 

- DP를 이차원 배열을 이용해서 만들었습니다.

 

 

무게보다 넣어야 하는 물건의 무게가 작거나 같은 경우, 즉 다른 물건을 더 넣을 수 있는 경우

 

dp[i][j] = Math.max( dp[i-1][j] , dp[i-1][j-b[i].w]+b[i].v);

 

이 점화식에 대해서 고민하면 문제를 풀 수 있다.