[코드트리/NOVICE HIGH] 쪼개어 배낭 채우기 2 (JAVA)

🔺 문제

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

 

🔺 코드

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        
        int[][] jewels = {{2, 3}, {6, 5}, {2, 4}, {3, 2}, {4, 3}};
        
        // 가치/무게 기준 내림차순 정렬
        Arrays.sort(jewels, new Comparator<int[]>() {
           @Override
           public int compare(int[] o1, int[] o2) { 
               return Double.compare((double) o2[1]/o2[0], (double) o1[1]/o1[0]);
           }
        });
        
        int size = 8;
        double answer = 0;
        
        while(size > 0) {
            boolean add = true;
            
            for(int i = 0 ; i < jewels.length ; i++) {
                // 무게가 가방 크기보다 작거나 같은 경우
                if(jewels[i][0] <= size) {
                    answer += jewels[i][1]; // 가치를 더함
                    size -= jewels[i][0];   // 사용 가능한 배낭 용량은 줄이기
                    add = true;
                }
                else {
                    // 🔔 보석 가치 * (사용 가능한 배낭 용량 / 무게)
                    answer += jewels[i][1] * ((double) size / jewels[i][0]); 
                    size = 0;
                    break;
                }
            }
            
            if(!add) break;
        }
        
        System.out.printf("%.3f", answer);
    }
}

 

🧩 해결 아이디어

쪼갤 수 있는 배낭 문제 (Fractional Knapsack) → 그리디

 

1. 배열을 무게 대비 가치가 높은 순 (= 가치/무게 기준)으로 내림차순 정렬한다. 🔔

 

2. 사용 가능한 배낭 무게가 0이 될 때까지 아래 과정을 반복한다.

 

   • 해당 보석 무게 ≤ 가방 크기인 경우

         - 정답에 해당 보석 가치를 더한다.

         - 사용 가능한 배낭 무게는 현재 보석 무게를 빼 줄인다.

 

    • 해당 보석 무게 ＞ 가방 크기인 경우

         - 정답에 현재 보석의 가치에 (현재 사용 가능한 배낭 용량 / 현재 보석의 무게)를 곱한다. 🔔

         - 사용 가능한 배낭 무게는 0으로 변경하고 반복문을 탈출한다.

 

 

---

🔺 다른 풀이들

- 꼭 나처럼 while문을 쓸 필요는 없고, 그냥 for문 순서대로 돌려서 해도 된다.

---

💬 느낀 점

언젠가 정리해야지 싶었던 Knapsack 문제....

풀고 나니 별 거 아닌 것 같다,,,!!!!

 

 

1회독	2회독	3회독	4회독	5회독
V