[코드트리 챌린지] 쪼개어 배낭 채우기 구현

1주차 실력진단 결과

문제

https://www.codetree.ai/cote/14/problems/implement-fractional-knapsack?&utm_source=clipboard&utm_medium=text

풀이 방법

• Fractional Knapsack 같은 경우는 가격/무게 값이 가장 큰 보석부터 담으면 쉽게 해결 가능
• 쪼개어 담는 것이 가능하므로 Fractional Knapsack으로 해결할 수 있다
• 가치/무게로 내림차순 정렬하여 보석을 채워주기

코드

import java.util.*;
import java.io.*;

public class Main {
    static class Info implements Comparable<Info> {
        int w, v;

        Info(int w, int v) {
            this.w = w;
            this.v = v;
        }

        @Override
        public int compareTo(Info info) {
            double x = (double) info.v / info.w - (double) this.v / this.w;
            if (x < 0) { // info의 가치/무게 값이 더 작으면 -1반환 / 순서유지
                return -1;
            } else if (x == 0) { // 가치/무게 값이 동일하면 0 반환
                return 0;
            } else { // info의 가치/무게값이 더 크면 1반환 / 순서 변경
                return 1;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());

        ArrayList<Info> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine(), " ");

            int w = Integer.parseInt(stk.nextToken());
            int v = Integer.parseInt(stk.nextToken());

            list.add(new Info(w, v));
        }
        Collections.sort(list);

        double ans = 0;
        for (int i = 0; i < list.size(); i++) {
            int w = list.get(i).w;
            int v = list.get(i).v;
            if (m >= w) {
                m -= w;
                ans += v;
            } else {
                ans += (double) m / w * v;
                break;
            }
        }
        System.out.printf("%.3f", ans);
    }
}

느낀점

정렬을 할 때 return this.w - info.w; 와 같은 방식만 사용해오다가 이런 방식으로 정렬을 구현하니 어려움을 겪었다. 더 노력해야겠다.