Isso parece uma variação do problema da mochila para mim. Resolvi o problema com a biblioteca do GA Jenetics :
import static java.util.Objects.requireNonNull;
import java.util.function.Function;
import java.util.stream.Collectors;
import org.jenetics.BitGene;
import org.jenetics.engine.Codec;
import org.jenetics.engine.Engine;
import org.jenetics.engine.EvolutionResult;
import org.jenetics.engine.Problem;
import org.jenetics.engine.codecs;
import org.jenetics.util.ISeq;
public class Springsteen
implements Problem<ISeq<Springsteen.Record>, BitGene, Double>
{
public static final class Record {
final String name;
final double price;
final ISeq<String> songs;
public Record(
final String name,
final double price,
final ISeq<String> songs
) {
this.name = requireNonNull(name);
this.price = price;
this.songs = requireNonNull(songs);
}
}
private final ISeq<Record> _records;
private final double _maxPricePerUniqueSong;
public Springsteen(final ISeq<Record> records, final double maxPricePerUniqueSong) {
_records = requireNonNull(records);
_maxPricePerUniqueSong = maxPricePerUniqueSong;
}
@Override
public Function<ISeq<Record>, Double> fitness() {
return records -> {
final double cost = records.stream()
.mapToDouble(r -> r.price)
.sum();
final int uniqueSongCount = records.stream()
.flatMap(r -> r.songs.stream())
.collect(Collectors.toSet())
.size();
final double pricePerUniqueSong = cost/uniqueSongCount;
return pricePerUniqueSong <= _maxPricePerUniqueSong
? uniqueSongCount
: 0.0;
};
}
@Override
public Codec<ISeq<Record>, BitGene> codec() {
return codecs.ofSubSet(_records);
}
public static void main(final String[] args) {
final double maxPricePerUniqueSong = 2.5;
final Springsteen springsteen = new Springsteen(
ISeq.of(
new Record("Record1", 25, ISeq.of("Song1", "Song2", "Song3", "Song4", "Song5", "Song6")),
new Record("Record2", 15, ISeq.of("Song2", "Song3", "Song4", "Song5", "Song6", "Song7")),
new Record("Record3", 35, ISeq.of("Song5", "Song6", "Song7", "Song8", "Song9", "Song10")),
new Record("Record4", 17, ISeq.of("Song9", "Song10", "Song12", "Song4", "Song13", "Song14")),
new Record("Record5", 29, ISeq.of("Song1", "Song2", "Song13", "Song14", "Song15", "Song16")),
new Record("Record6", 5, ISeq.of("Song18", "Song20", "Song30", "Song40"))
),
maxPricePerUniqueSong
);
final Engine<BitGene, Double> engine = Engine.builder(springsteen)
.build();
final ISeq<Record> result = springsteen.codec().decoder().apply(
engine.stream()
.limit(10)
.collect(EvolutionResult.toBestGenotype())
);
final double cost = result.stream()
.mapToDouble(r -> r.price)
.sum();
final int uniqueSongCount = result.stream()
.flatMap(r -> r.songs.stream())
.collect(Collectors.toSet())
.size();
final double pricePerUniqueSong = cost/uniqueSongCount;
System.out.println("Overall cost: " + cost);
System.out.println("Unique songs: " + uniqueSongCount);
System.out.println("Cost per song: " + (cost/uniqueSongCount));
System.out.println("Records: " + result.map(r -> r.name).toString(", "));
}
}
A função fitness é simples, o número de músicas únicas, restritas pelo preço máximo por música, que você está disposto a pagar. A execução do código imprimirá a seguinte saída:
Overall cost: 37.0
Unique songs: 15
Cost per song: 2.466666666666667
Records: Record2, Record4, Record6