[SWEA] 3282 : 0/1 Knapsack

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJAVpqrzQDFAWr 

SW Expert Academy

처음엔 백트래킹과 index가 부피를 의미하는 일차원배열의 DP를 이용해서 해결하려 했으나 실패했다.

백트래킹을 사용하기엔 주어진 N의 값이 너무 컸어서 올바른 접근이 아니었다.

이차원배열의 DP를 이용하는 것이 핵심이었는데 어떻게 하면 이전의 값들을 이용하면서 DP를 채울 수 있을지 고민했다.

 DP[N + 1][K + 1] (n -> 1 ~ N, k -> 1 ~ K)에서 탐색중인 물건의 부피가 k이하일 때

1. 해당 물건을 넣을 때의 가치값, 이때 해당 물건을 그냥 넣으면 부피가 초과될 수 있으므로 해당 물건의 부피를 제외했을 때의 최대가치값과 해당 물건의 가치값의 합을

2. 해당 물건을 넣지 않고 현재 해당 부피가 가지고 있는 최대가치값과 비교하여

더 큰 값을 채워넣으면 됐다.

실제 문제를 만났을 때 내가 이런 생각을  바로 할 수 있도록 노력해야겠다. 고려해야 할 데이터가 많다면 이차원배열의 DP도 고려하면서 문제를 풀어야겠다.

 

내 코드

메모리 : 19384 KB

시간 : 120 ms

코드길이 : 1357 B

 

[내 코드]

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

public class Solution {
	static int N, K;
	static int[] v, c;
	static int[][] DP;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			sb.append('#').append(t).append(' ');
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			v = new int[N + 1]; //부피
			c = new int[N + 1]; //가치
			DP = new int[K + 1][N + 1]; //해당 부피일 때 최대 가치
			
			for(int n = 1; n <= N; n++) {
				st = new StringTokenizer(br.readLine());
				v[n] = Integer.parseInt(st.nextToken());
				c[n] = Integer.parseInt(st.nextToken());
			}
			
			choice();
			
			sb.append(DP[K][N]).append('\n');
		}
		System.out.print(sb);
	}
	static void choice() {
		for(int k = 1; k <= K; k++) {//부피(행)
			for(int n = 1; n <= N; n++) {//포함된 물건(열)
				if(v[n] <= k){//해당 물건의 부피가 정해진 부피에 들어갈 수 있으면
					//해당물건을 포함하지 않고 정해진 부피를 채울 때의 가치최대값
					//해당물건이 들어갈 부피를 제외한 부피의 가치최댓값에 해당물건의 가치를 더한 값
					DP[k][n] = Math.max(DP[k][n - 1], DP[k - v[n]][n - 1] + c[n]);
				}
				else
					DP[k][n] = DP[k][n - 1];
				}
				
			}
		}
}