[Java]백준 BaekJoon.AC 12865 : 평범한 배낭 (다이나믹 프로그래밍, knapsack)

 

 

 

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

12865번: 평범한 배낭

 

 

다이나믹 프로그래밍이라길래 Queue 이용해서 열심히 코딩했는데..

작동도 잘 되는거 같고 쉽게 풀려서 기분이 좋았다!^^

늘 그렇듯..^^ 잘 풀린 코드는 틀린다. 메모리 초과됐다..ㅠ

 

<틀린 코드>

그래도 중첩 클래스 다시 한 번 써보고 지금껏 익혔던 스킬들..? 적용해봐서 통한스럽진 않다..ㅋㅠ

 

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

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());
		Queue<Bag> queue = new LinkedList<>();
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			if(queue.isEmpty() && w<=K) {
				queue.add(new Bag(w, v));
				continue;
			}
			
			int s = queue.size();
			
			for(int j=0; j<s; j++) {
				Bag temp = queue.poll();
				
				if(temp.w + w <= K) {
					queue.add(new Bag(temp, w, v));
				}
				
				queue.add(temp);
				
				if(w<K) {
					queue.add(new Bag(w, v));
				}

			}
			
		}
		
		int vvv = 0;
		for(Bag b : queue) {
			if(vvv<b.v) {
				vvv = b.v;
			}
		}
		
		System.out.print(vvv);
	}
}

class Bag {
	
	int w, v;
	
	Bag(int w, int v) {
		this.w = w;
		this.v = v;
	}
	
	Bag(Bag b) {
		this.w = b.w;
		this.v = b.v;
	}
	
	Bag(Bag b, int w, int v){
		this.w = b.w + w;
		this.v = b.v + v;
	}
}

 

도저히 이 상태에서 메모리를 줄일 방법을 못찾겠더라..

내 방법이 아예 틀린 것인가 싶어 다른 코드들을 찾아봤다.

역시 방식이 다르...

이번 문제는 새로운 알고리즘 알아가는 느낌으로 최대한 이해하고 따라하는 데에 집중했다.

 

<참고 링크>

https://st-lab.tistory.com/141

참고 사이트에서 가져온, 깔끔하게 공식화 된..!

 

2차원 배열로 계산하는 문제는 복잡할수록 어렵지만 재밌다..!

knapsack이란 알고리즘을 새로 배웠다.

알고리즘 이해만 도움을 받고 풀이는 내가 직접 해봤다.

Bottom-Up 형식으로 해결했고,

DP배열은 밑에서 오른쪽으로 향했다. 

 

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

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());
		int K = Integer.parseInt(st.nextToken());
		
		int[][] DP = new int[N+1][K+1];
		int[] weight = new int[N+1];
		int[] value = new int[N+1];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			weight[i] = Integer.parseInt(st.nextToken());
			value[i] = Integer.parseInt(st.nextToken());
		}
		
		
		for(int k=1; k<=K; k++) {
			for(int m=1; m<=N; m++) {
				
				DP[m][k] = DP[m-1][k];
				
				if(weight[m]<=k) {
					int restW = k-weight[m];
					if(DP[m-1][restW] + value[m] > DP[m][k]) {
						DP[m][k] = DP[m-1][restW] + value[m];
					}
				}
			}
		}
		
		System.out.print(DP[N][K]);
	}
}