[swexpert] 3282. 0/1 knapsack (dp, java)

각 물건의 무게를 쪼갤 수 없고 넣냐 빼냐로 결정하는 0/1 배낭 문제이다.

dfs나 백트래킹으로는 2**n 승으로 오래걸려 시간 초과가 난다.

dp로 풀어야만 풀리는 문제 

 

dp[i][j]: 물건 i 번째에서 배낭 무게가 j일 때의 물건 가치 

 

dp를 나누는 경우의 수 

 

1. i 번째 물건이 무게 j보다 클 때: i 번째 물건을 무게가 j인 경우에 넣을 수 없어 이전 물건에서의 무게가 j인 가치를 넣어준다. dp[i][j]=dp[i-1][j];

2. i 번째 물건이 무게 j보다 같거나 작을 때: dp[i][j]=Math.max(dp[i][j-w[i]]+cost[i],dp[i-1][j]);

 

이 문제는 물건 무게가 0인 경우가 없는데 만약 있는 문제라면 dp[i][j]=0; 으로 초기화해준다.

 

import java.util.Scanner;

public class Solution {
	static int n,k,t;
	static int[] v;
	static int[] c;
	static int[][] dp;
	static int answer;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			k=sc.nextInt();
			dp=new int[n+1][k+1];
			answer=Integer.MIN_VALUE;
			v=new int[n+1];// 부피
			c=new int[n+1];// 가치
			for (int i = 1; i <= n; i++) {
				v[i]=sc.nextInt();//부피(무게라칩시다)
				c[i]=sc.nextInt();//가치
			}
			for (int i = 1; i <= n; i++) {//몇 번째 가방
				for (int j = 0; j <= k; j++) {//현재 구하는 무게)
					if(v[i]>j) { //무게가 커서 경우의 수에 포함안됨
						dp[i][j]=dp[i-1][j];
					}
					else {//포함가능. 어떤게 더 이득일까?
						dp[i][j]=Math.max(dp[i-1][j-v[i]]+c[i],dp[i-1][j]);
					}
				}
			}

			for (int i = 1; i <= k; i++) {
            // n번째 물건까지 모두 고려한 것들 중 무게가 k이하인 모든 경우에서 가치가
            //가장 높은 것을 찾아 반환한다.
				if(answer<dp[n][i])answer=dp[n][i];
			}
			System.out.printf("#%d %d\n",tc,answer);
		}
	}

}