Вы можете решить задачу с помощью рекурсии. Если у вас есть метод, который может выбрать наилучшую комбинацию элементов для данного бюджета, реализуйте его следующим образом:
Выполните итерации по элементам и для каждого элемента, проверьте, находится ли он в рамках бюджета, и, если это так, удалитеэто из имеющихся предметов и вычесть его расходы из бюджета. Затем попросите рекурсивно найти наилучшее сочетание оставшихся предметов с оставшимся бюджетом и объединить его с текущим предметом. Проверьте, лучше ли полученная комбинация, чем предыдущая, и сохраните только лучшую.
Это можно оптимизировать, используя список элементов, отсортированных по цене, что позволяет прекратить итерации, когда все остальные элементы стоят дороже, чемнаш текущий бюджет. Со списком, остальные элементы могут быть выражены через индекс без необходимости создавать новые коллекции. Нам не нужно рассматривать элементы до текущей, так как это приведет к комбинациям, которые мы уже проверяли ранее:
public static Set<String> select(Map<String,Integer> available, int budget) {
List<Map.Entry<String,Integer>> temp = new ArrayList<>(available.entrySet());
temp.sort(Map.Entry.comparingByValue());
Choice c = selectImpl(temp, 0, budget);
return c == null? Collections.emptySet(): c.items;
}
private static Choice selectImpl(
List<Map.Entry<String, Integer>> availTemp, int start, int budget) {
Choice c = null;
for(int ix = start; ix < availTemp.size(); ix++) {
Map.Entry<String, Integer> e = availTemp.get(ix);
if(e.getValue() > budget) return c;
Choice sub;
int cost = e.getValue(), remaining = budget - cost;
if(remaining == 0) return new Choice(e.getKey(), budget);
sub = selectImpl(availTemp, ix + 1, remaining);
if(c == null || c.cost < (sub == null? cost: sub.cost + cost))
c = sub == null? new Choice(e.getKey(),e.getValue()): sub.add(e.getKey(),cost);
}
return c;
}
private static final class Choice {
final Set<String> items;
int cost;
Choice(String key, int c) {
items = new HashSet<>();
items.add(key);
cost = c;
}
Choice add(String key, int c) {
items.add(key);
cost += c;
return this;
}
}
Это можно использовать как
Map<String,Integer> available = Map.of(
"Item A", 450, "item B", 300, "Item C", 350, "item D", 200);
int budget = 900;
Set<String> picked = select(available, budget);
System.out.println("With "+budget+ ", buy "+picked
+", consuming "+picked.stream().mapToInt(available::get).sum());