[SW expert Academy] SWEA 3282번 0/1 Knapsack 자바(Java)

[D3] 0/1 Knapsack - 3282

문제 링크

성능 요약

메모리: 31,384 KB, 시간: 171 ms, 코드길이: 1,024 Bytes

제출 일자

2023-11-09 10:36

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

import java.util.Scanner;
class Solution
{
	public static void main(String args[]) throws Exception {
		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[] weight = new int[n+1];
            int[] cost = new int[n+1];
            
            for(int i = 1; i <= n; i++){
                weight[i] = sc.nextInt();
                cost[i] = sc.nextInt();
            }
            int[][] dp = new int[n+1][k+1];
            for(int i = 1; i <= n; i++){
                for(int j =1; j <= k; j++){
                    if(weight[i] > j){
                        dp[i][j] = dp[i-1][j];
                    }else{
                        dp[ i ][ j ] = Math.max(dp[ i - 1 ][ j - weight [ i ] ] + cost[i]
                                                , dp[ i - 1 ][ j ] );
                    }
                }
            }
            System.out.println("#" + tc + " " + dp[n][k]);
		}
    }
}

 

i / j	1	2	3	4
1	2	2	2	2
2	2	2	2	3
3	2	2	2	4
4	2	4	4	5
5	2	4	6	6

 

i = 아이템 번호들

j = 각 무게별로 들 수 있는 아이템의 가중치