[AlgoSpot] 여행 짐 싸기

문제 설명

알고리즘 문제 해결 전략 - 동적 계획법
https://algospot.com/judge/problem/read/NUMB3RS

문제 풀이

• 동적 계획법 문제이다.
• bottom-up방식으로 0/1 냅색 알고리즘을 구현하였다. 점화식은 다음과 같다.

  dp[W][index] : index 포함 이후 물건들로 최대 W 무게 만큼 넣었을 때, 가치합의 최대.
  dp[W][index] = MAX(dp[W][index+1], dp[W-w[index]][index+1] + v[index])

• 추가로, 결과 출력을 위해 최적해를 따라 출력하는 함수를 따로 두었다.

소스 코드 (JAVA)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static int C, N, W;
    public static int w[] = new int[101];
    public static int v[] = new int[101];
    public static String n[] = new String[101];
    public static int dp[][] = new int[1001][101];

    public static void init() {
        for (int i = 0; i <= W; i++)
            for (int j = 0; j <=N; j++)
                dp[i][j] = -1;
    }

    public static void printResult() {
        int rw = W, ind = 0;
        List<Integer> resList = new ArrayList<>();
        int resVal = dp[W][0];
        while(true) {
            //결과 출력
            if (ind == N) {
                System.out.println(resVal + " " + resList.size());
                for (int i = 0; i < resList.size(); i++)
                    System.out.println(n[resList.get(i)]);
                break;
            }

            if (dp[rw][ind] == dp[rw][ind+1] || ind == N - 1)
                ind++;
            else {
                rw -= w[ind];
                resList.add(ind);
                ind++;
            }
        }
    }

    public static int solve(int rw, int ind) {
        //기저조건 : 끝까지 도달 했을때
        if (ind == N) return 0;
        if (dp[rw][ind] != -1) return dp[rw][ind];
        int result = solve(rw, ind+1);
        if (rw >= w[ind])
            result = Math.max(result, solve(rw - w[ind], ind + 1) + v[ind]);
        dp[rw][ind] = result;
        return dp[rw][ind];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        C = sc.nextInt();
        for (int c = 0; c < C; c++) {
            N = sc.nextInt();
            W = sc.nextInt();
            for (int i = 0; i < N; i++) {
                n[i] = sc.next();
                w[i] = sc.nextInt();
                v[i] = sc.nextInt();
            }
            init();
            solve(W, 0);
            printResult();
        }
    }
}