Algoritma serakah apa yang memenuhi properti pilihan serakah tetapi tidak memiliki substruktur yang optimal?

Berdasarkan buku Pengantar Algoritma , kebenaran dari algoritma serakah membutuhkan masalah untuk memiliki dua properti:

1. properti pilihan serakah
2. substruktur optimal

Sangat mudah untuk menghasilkan contoh-contoh balasan yang solusi serakah gagal karena kurangnya properti pilihan serakah, misalnya masalah 0/1 ransel. Tetapi saya menemukan kemungkinan lain cukup sulit untuk dibayangkan. Adakah yang bisa memberi saya masalah dan algoritma serakah yang sesuai yang memenuhi properti pertama tetapi bukan yang kedua?

Salah satu penaksir standar dalam statistik yang kuat adalah jenis rata-rata terpangkas di mana Anda memilih subset mayoritas dari serangkaian angka input sedemikian rupa untuk meminimalkan perbedaan maksimum antara dua angka yang dipilih, dan kemudian mengambil rata-rata dari yang dipilih bagian Ada langkah pertama pilihan serakah yang mudah: pilih median sebagai bagian dari subset Anda. Tapi begitu Anda telah membuat pilihan itu, masalah yang tersisa bukan dari jenis yang sama (yaitu kita tidak memiliki substruktur yang optimal), jadi tidak ada metode yang jelas untuk melanjutkan algoritma ini dengan rakus. Khususnya tidak berfungsi untuk tetap memilih median poin yang tersisa. (Strategi median serakah yang diulang, dilakukan dengan sedikit perhatian, memberikan rata-rata interkuartil yang juga kuat tetapi tidak memecahkan masalah yang sama dan memiliki titik rincian yang lebih rendah.)