C++ 轉 Java：分數背包問題 (貪婪演算法) 完整移植代碼

原 C++ 代碼為經典 **分數背包** : 物品可拆分，按單價遞減排序，裝滿背包即停止。以下提供對應的 Java 完整實作 (JDK 8+)。

核心邏輯對照

• C++ `struct` + `operator<` → Java `static class` 實作 `Comparable`。
• C++ `sort(buf, buf+n)` → Java `Arrays.sort(arr)`。
• C++ `scanf/printf` → Java `Scanner/System.out.println` (大量資料建議 `BufferedReader`)。
• C++ `while(~scanf("%d",&v) && v)` → Java `while(scanner.hasNextInt() && (v=scanner.nextInt())!=0)`。

完整 Java 代碼

import java.util.*;

public class FractionalKnapsack {
    static class Jewelry implements Comparable<Jewelry> {
        int price;   // 單價
        int volume;  // 體積/重量

        @Override
        public int compareTo(Jewelry o) {
            return Integer.compare(o.price, this.price); // 單價降序
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringBuilder out = new StringBuilder();
        Jewelry[] items = new Jewelry[101]; // 題目上限

        while (in.hasNextInt()) {
            int V = in.nextInt(); // 背包容量
            if (V == 0) break;
            int n = in.nextInt(); // 物品數
            for (int i = 0; i < n; i++) {
                items[i] = new Jewelry();
                items[i].price = in.nextInt();
                items[i].volume = in.nextInt();
            }
            Arrays.sort(items, 0, n); // 只排序有效區間

            int idx = 0;
            long ans = 0; // 總值可能超過 int
            while (V > 0 && idx < n) {
                Jewelry cur = items[idx];
                if (V >= cur.volume) {
                    V -= cur.volume;
                    ans += 1L * cur.price * cur.volume;
                } else {
                    ans += 1L * V * cur.price;
                    V = 0;
                }
                idx++;
            }
            out.append(ans).append('\n');
        }
        System.out.print(out);
        in.close();
    }
}

關鍵細節

效能與正確性提醒

• 總價值 `ans` 使用 `long` (64 位) 防止溢位 (price, volume ≤ 10^4, V ≤ 10^5 → ans ≤ 10^14)。
• `Arrays.sort(items, 0, n)` 僅排序前 n 個有效元素，避免排序殘留 null 導致 NPE。
• 大量測資建議換用 `FastScanner` (自訂緩衝讀取) 替代 `Scanner`。

分數背包貪婪證明：單價最高的優先裝入，局部最優推導全域最優。Java 移植只需注意排序方向與型別寬度。