Qual algoritmo ganancioso satisfaz a propriedade de escolha gananciosa, mas não possui uma subestrutura ideal?

Com base no livro Introdução aos algoritmos , a correção de um algoritmo ganancioso exige que um problema tenha duas propriedades:

1. propriedade escolha ganancioso
2. subestrutura ideal

É fácil criar exemplos contrários para os quais uma solução gananciosa falha devido à falta da propriedade de escolha gananciosa, por exemplo, o problema da mochila 0/1. Mas acho a outra possibilidade bastante difícil de imaginar. Alguém pode me dar um problema e um algoritmo ganancioso correspondente que satisfaça a primeira propriedade, mas não a segunda?

Um dos estimadores padrão em estatísticas robustas é um tipo de média aparada, na qual você escolhe um subconjunto majoritário de um conjunto de números de entrada de forma a minimizar a diferença máxima entre dois números selecionados e, em seguida, leva a média do número selecionado. subconjunto. Há um primeiro passo fácil para a escolha gananciosa: escolha a mediana como parte do seu subconjunto. Mas uma vez que você fez essa escolha, o problema restante não é do mesmo tipo (ou seja, não temos subestruturas ideais), então não há um método óbvio de continuar esse algoritmo com avidez. Em particular, não funciona para escolher as medianas dos pontos restantes. (A estratégia mediana repetida e gananciosa, feita com um pouco de cuidado, fornece a média interquartil que também é robusta, mas não resolve o mesmo problema e tem um ponto de ruptura mais baixo.)