현대 오토에버 24.06.29

현재 회사에 새로 입사한 K명의 신입 사원들에게 보급품이 N개 주어지는데 각 보급품은 무게와 가치가 있어. 총 무게를 M 만큼 담을 수 있는 가방이 있어. 최대 가치를 구하게 해줘. 각 가방은 정해진 무게 M을 초과할 수 없고, 보급품은 쪼개서 담을 수 없어.

 

1<= N, M <= 50 1 <= K <= 3 1<= W[i], V[i] <= 50

첫 줄은 N, K, M 이고

이후 N개의 줄에 W, V가 주어져

입력 예시

5 2 5

4 5

3 4

2 1

5 7

1 1

 

정답 13

 

package com.example.algorithm;

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

public class hd_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(st.nextToken()); 
        int K = Integer.parseInt(st.nextToken()); 
        int M = Integer.parseInt(st.nextToken()); 

        int[] W = new int[N];
        int[] V = new int[N]; 

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(reader.readLine());
            W[i] = Integer.parseInt(st.nextToken());
            V[i] = Integer.parseInt(st.nextToken());
        }

        // 각 사원이 사용할 수 있는 아이템 추적을 위해 사용된 아이템 여부를 관리
        boolean[] used = new boolean[N];

        // 최종 최대 가치를 저장할 변수
        int totalMaxValue = 0;

        // 각 사원마다 독립적으로 배낭 문제를 해결
        for (int k = 0; k < K; k++) {
            int[][] dp = new int[M + 1][N + 1];

            for (int i = 0; i < N; i++) {
                if (!used[i]) { // 아이템이 사용되지 않았을 때만 고려
                    for (int w = M; w >= W[i]; w--) {
                        for (int j = N; j >= 1; j--) {
                            dp[w][j] = Math.max(dp[w][j], dp[w - W[i]][j - 1] + V[i]);
                        }
                    }
                }
            }

            // 현재 사원의 최대 가치를 찾고, 그 아이템들을 사용된 것으로 표시
            int maxValue = 0;
            for (int w = 0; w <= M; w++) {
                for (int j = 0; j <= N; j++) {
                    if (dp[w][j] > maxValue) {
                        maxValue = dp[w][j];
                    }
                }
            }
            totalMaxValue += maxValue;

            // 사용된 아이템들을 역추적 -> 다른 사원이 사용할 수 없도록 설정
            for (int w = M; w >= 0; w--) {
                for (int j = N; j >= 1; j--) {
                    if (dp[w][j] != dp[w][j - 1]) {
                        for (int i = 0; i < N; i++) {
                            if (!used[i] && w >= W[i] && dp[w][j] == dp[w - W[i]][j - 1] + V[i]) {
                                used[i] = true;
                                w -= W[i];
                                break;
                            }
                        }
                    }
                }
            }
        }

        System.out.println(totalMaxValue);
    }
}