그리디 - 분할 가능 배낭

public class Knapsack {
    public static void main(String[] args) {
        int[] value = {50, 60, 140};
        int[] weight = {5, 10, 20};
        int limit = 30;
        fractionalKnapsack(value, weight, limit);
    }

    static void fractionalKnapsack(int[] value, int[] weight, int limit) {
        int result = 0;
        int w = limit; // 남은 무게

        Integer[][] arr = new Integer[value.length][3]; 

        for (int i = 0; i < arr.length; i++) {
            arr[i][0] = value[i] / weight[i];
            arr[i][1] = value[i];
            arr[i][2] = weight[i];
        }

        Arrays.sort(arr, (o1, o2) -> o2[0] - o1[0]);

        for (int i = 0; i < arr.length && w > 0; i++) {
            if (arr[i][2] < w) { // 남은 무게보다 물건 무게가 작음
                result += arr[i][2] * arr[i][0]; // 무게 * 무게 당 가치
                w -= arr[i][2];
            } else {
                result += w * arr[i][0];
                w = 0;
            }
        }

        System.out.println("======================================");
        System.out.println(result);
    }
}