SWEA level3 - 3282 0/1 knapsack

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJAVpqrzQDFAWr&categoryId=AWBJAVpqrzQDFAWr&categoryType=CODE

SW Expert Academy

1. 종류

동적프로그래밍

 

2. 풀이

dp의 특징을 잘 나타낸 문제다.

고려해야할 변수가 2개(부피, 가치)이기 때문에 2차원 배열을 사용해야 한다.

3. 코드

import java.util.Arrays;
import java.util.Scanner;

public class swea3282_knapsack {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			int n=sc.nextInt();
			int k=sc.nextInt();
			int dp[][] = new int[101][1001];
			int arr[][] = new int[n+1][2];
			for (int i = 1; i <= n; i++) {
				arr[i][0] = sc.nextInt();//부피
				arr[i][1] = sc.nextInt();//가치
			}
			Arrays.sort(arr, (o1, o2)->{
				return o1[0]-o2[0];
			});
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= k; j++) {
					if(j-arr[i][0]>=0)
						dp[i][j] = Math.max(dp[i-1][j-arr[i][0]] + arr[i][1], dp[i][j]);
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j]);
				}
			}
			System.out.println("#"+tc+" "+dp[n][k]);
		}
	}
}

 

현재 물건을 선택한 경우

if(j-arr[i][0]>=0)
	dp[i][j] = Math.max(dp[i-1][j-arr[i][0]] + arr[i][1], dp[i][j]);

 

 

현재 물건을 선택 안 한 경우

dp[i][j] = Math.max(dp[i-1][j], dp[i][j]);