public class PotongBesi {

    // Harga jual besi per panjang 1..8 (meter), index 0 tidak dipakai.
    static final int[] HARGA = {0, 1000, 5000, 8000, 9000, 10000, 17000, 17000, 20000};

    public static void main(String[] args) {
        int n = HARGA.length - 1;

        int[] pendapatan = new int[n + 1]; // pendapatan[k] = hasil terbaik untuk besi panjang k
        int[] potonganPertama = new int[n + 1]; // potongan pertama pada solusi terbaik panjang k

        for (int k = 1; k <= n; k++) {
            int terbaik = Integer.MIN_VALUE;
            for (int p = 1; p <= k; p++) {
                int kandidat = HARGA[p] + pendapatan[k - p];
                if (kandidat > terbaik) {
                    terbaik = kandidat;
                    potonganPertama[k] = p;
                }
            }
            pendapatan[k] = terbaik;
        }

        System.out.println("=== Rod cutting bottom-up, panjang total " + n + " meter ===");
        System.out.println("Harga  : " + java.util.Arrays.toString(java.util.Arrays.copyOfRange(HARGA, 1, n + 1)));
        System.out.println();
        System.out.printf("%-9s %-11s%n", "Panjang", "Pendapatan");
        for (int k = 1; k <= n; k++) {
            System.out.printf("%-9d Rp%-10d%n", k, pendapatan[k]);
        }
        System.out.println();
        System.out.println("Rekonstruksi potongan untuk besi 8 meter:");
        int sisa = n;
        while (sisa > 0) {
            System.out.println("  potong " + potonganPertama[sisa] + " meter -> Rp" + HARGA[potonganPertama[sisa]]);
            sisa -= potonganPertama[sisa];
        }
        System.out.println("Total: Rp" + pendapatan[n]);
    }
}