코드트리 [자바 java] 쪼개어 배낭 채우기 구현

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

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 보석의 수와 배낭의 크기가 주어지고, 이 배낭에 담을 수 있는 보석들의 가치의 최댓값을 구하는 문제입니다.

 

저는 그리디알고리즘을 사용하였습니다.

 보석을 쪼갤 수 있으므로, 보석별로 부피당 가치를 구하고, 이를 오름차순으로 정렬해서 최대한 가치가 높은 것으로만 가방을 채웠습니다. 

 

처음에는 TreeMap을 이용해서 문제를 풀었습니다.

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int[][] arr = new int[n][2];

        TreeMap<Double,Integer> t = new TreeMap<>();

        double[] l = new double[n];

        for(int i =0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            t.put(((double)arr[i][1]) / ((double)arr[i][0]), i);
            l[i] = (double)arr[i][1] / (double)arr[i][0];
        }

        Arrays.sort(l);

        double p = 0;

        for(int i =n-1;i>=0;i--){
            int k = t.get(l[i]);
           // System.out.println(l[i]);
            for(int j = arr[k][0];j>=1;j--){
                if(j <= m){
                    m -= j;
                    p += j * l[i]; 
                    break;
                }
            }
            if(m == 0) break;
        }

        System.out.printf("%.3f",p);



    }
}

하지만 위 코드에 잘못된 부분이 있었습니다. 

TreeMap에는 중복을 제외한다는 특징이 있는데, 이로 인해 간과되는 보석들이 있었습니다.

앞으로 TreeMap를 사용할 때에는 중복을 제외할 수 있는지 꼭 확인해봐야겠습니다.

 

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

public class Main {

    static class j implements Comparable<j>{
        int w;
        int p;
        j(int w, int p){
            this.w = w;
            this.p = p;
        }

        @Override
        public int compareTo(j n){
            double x = (double)n.p/(double)n.w - (double)this.p /  (double)this.w;
            if(x < 0) return -1;
            else if(x == 0) return 0;
            else return 1;
        }

    }

    static ArrayList<j> jj = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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


        for(int i =0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            jj.add(new j(a,b));
        }

        Collections.sort(jj);
        
        double pp = 0;

        for(int i =0;i<n;i++){
            //System.out.println(m);
           int w = jj.get(i).w;
           int v = jj.get(i).p;

           if(m >= w){
            pp+= v;
            m -= w;
           }
           else{
            for(int j = w-1;j>=0;j--){
                if(m >= j){
                    pp += ((double)v/(double)w) * j;
                    m -= j;
                    break;
                }
            }
           }
        }

        System.out.printf("%.3f",pp);



    }
}