Выберите один элемент каждого типа с наибольшим значением без превышения бюджета

Question

Учитывая приведенный ниже список элементов, бюджет B и список типов элементов (T1, T2, T3 ... TN), выберите 1 элемент каждого типа, который обеспечивает наибольшую ценность (самый дорогой) без превышения бюджета.

[
  {
    "id": "1",
    "types": "T1",
    "price": 1000,
  },
  {
    "id": "2",
    "types": "T2",
    "price": 109292,
  },
  {
    "id": "3",
    "types": "T3",
    "price": 7228,
  },
  {
    "id": "4",
    "types": "T4",
    "price": 1000,
  },
]

Изучены проблемы с рюкзаком и нет уверенности в том, что это полная проблема NP.

Answer 1

Просто используйте filter, чтобы найти все элементы, которые не превышают бюджет, затем sort в порядке убывания и возьмите первый элемент:

const array = [{
    "id": "1",
    "types": "T1",
    "price": 1000,
  },
  {
    "id": "2",
    "types": "T2",
    "price": 109292,
  },
  {
    "id": "3",
    "types": "T3",
    "price": 7228,
  },
  {
    "id": "4",
    "types": "T4",
    "price": 1000,
  },
];

const budget = 9000;

var budgetMatch = array.filter(({ price }) => price <= budget);
budgetMatch.sort(({ price: a}, { price: b}) => b - a);

var highestPrice = budgetMatch[0];

console.log(highestPrice);