Прежде всего, некоторый контекст проблемы:
Я работаю в системе с несколькими типами ресурсов (A, B, C...). У меня есть некоторые требования к ресурсам, и мне нужно определить, могу ли я их себе позволить.
Для этого у меня есть несколько источников, каждый из которых может предоставить более одного типа ресурса, но мне нужно выбрать, какой из них я использую для каждого ресурса.
Например, если мне нужно заплатить 1A, 2B и 0C (представленные как (1,2,0)) и у меня есть эти источники:
- (1,1,0) //Означает, что я должен выбрать продукт A или B
- (0,1,1) //Означает, что я должен выбрать продукт B или C
- (1,1,0)
Очевидно, что я должен использовать источник 2 для ресурса B, и я могу выбрать для 1 и 3, какой из них производит A и B.
Мой подход к реализации этого состоит в том, чтобы рассматривать его как график зависимости, где описанная выше ситуация представлена следующим образом:
Итак, я перебираю ресурсы, и для каждого ресурса я перебираю ссылки, идущие к нему. Если удаление текущего узла для текущего ресурса означает, что у других ресурсов достаточно оставшихся доходящих ссылок, чтобы оплатить оставшуюся стоимость, я использую его.
В предыдущем примере я сначала пытаюсь использовать источник 1 для ресурса A. B все еще имеет 2 ссылки, поэтому я могу это сделать. Для оплаты остаются только ресурсы типа B, поэтому я использую оставшиеся источники для оплаты B.
Хорошо здесь, но теперь мне нужно работать в новом сценарии, где есть два типа источников, каждый из которых производит один тип ресурса по стоимости 1 или по цене 2, и мне нужно минимизировать общую стоимость.
Небольшое изменение примера может быть таким: 
Решение, основанное на здравом смысле, должно заключаться в том, чтобы использовать 1 и 2 для оплаты B и использовать 3 для оплаты A при общей стоимости 1, но в моей реализации, как описано выше, источник 1 используется для оплаты A, потому что B все еще имеет 2 ссылки на это, поэтому в конце я должен использовать источник 3 со стоимостью 2.
По возможности следует избегать решений, подразумевающих перебор всех возможных комбинаций.
Знаете ли вы о какой-либо общей алгоритмической задаче с известным решением, которое можно применить к этому случаю? Или как улучшить мое фактическое решение для работы в этом новом сценарии? Или я должен использовать другой другой подход?
