Блог

У меня есть набор данных с 3 столбцами (Имя, Значение, Стоимость). Я пытаюсь найти способ вернуть 15 имен из набора данных, которые обеспечивают наибольшее значение при общей стоимости 200 долларов или меньше.

В идеале я хотел бы вернуть, скажем, 20 лучших уникальных записей из комбинации 15 имен, которые обеспечивают наибольшее комбинированное значение.

Пример Набора Данных:

То, что вы описали, известно как проблема с рюкзаком. За исключением некоторых особых случаев, эта проблема, как известно, является NP-полной (википедия). Это означает, что не существует «быстрого» алгоритма, который гарантированно даст вам решение с наивысшим значением.

Быстро в этом случае можно рассматривать как «значительно лучше, чем пробовать все возможные комбинации и выбирать лучшую». Это может быть практично для небольшого набора данных и мощного компьютера, но для набора данных со 100 именами может потребоваться больше недели.

Поскольку вы указали тег dplyr, лучшее, что вы, вероятно, можете сделать, это выбрать те товары, которые имеют наилучшее соотношение цены и качества. Вероятно, что-то вроде следующего:

 output = dataset  %>%
  mutate(ratio = value / cost) %>%
  arrange(-ratio) %>% # sort descending
  head(15) %>% # limit to at most 15 names
  mutate(cumulative = cumsum(cost)) %>% # cost of names from best ratio to worst
  filter(cumulative <= 200) %>% # discard least cost effective names to keep total cost under $200
  select(names)