Алгоритм C # - найти наименьшее количество необходимых объектов

Question

Допустим, у меня есть следующий код.

var numberToGetTo = 60; 
var list = new[] {10, 20, 30, 40, 50};

Я хочу иметь возможность вернуть 50 и 10 из списка в = 60.

Если бы numberToGetTo было 100, я бы хотел вернуть 50, 50.

Если бы numberToGetTo было 85, я бы хотел вернуть 50, 40.

Я хочу вернуть наименьшее количество чисел из списка, необходимое для перехода к «numberToGetTo», оставаясь при этом ближе (равнее или выше) к нему.

Возможно ли сделать что-то подобное с Linq?

Answer 1

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

Answer 2

Вот реализация, которая использует Linq, чтобы быть максимально чистым. Он не пытается оптимизировать производительность на больших входах.

Я предполагаю, что вы не будете использовать этот алгоритм для больших входов в любом случае, так как проблема в NP-Complete, и поэтому ясность - правильная цель. Мой алгоритм O (n ^ 2), и рекурсивный в этом.

    static IEnumerable<int> Knapsack(IEnumerable<int> items, int goal)
    {
        var matches = from i in items
                      where i <= goal
                      let ia = new[] {i}
                      select i == goal ? ia : Knapsack(items, goal - i).Concat(ia);

        return matches.OrderBy(x => x.Count()).First();
    }

Answer 3

Эта проблема, как заявлено в настоящее время, на самом деле тривиальна. Самый простой способ получить значение «равно или больше» цели - найти наибольшее число A в списке и вставить его в список ответов N раз, где N - это наименьшее N, такое, что N * A> цель.

Я подозреваю, что это не то, чего действительно хочет оригинальный плакат. Если проблема повторяется, чтобы как-то измерить «близость» различных ответов и провести различие в том, являются ли «более близкие» ответы или ответы, имеющие меньшие числа, «лучше», то это становится более жестким. Например, если целевое значение равно 100, ответ [55,55] лучше или хуже ответа [20,20,20,20,20]?

Answer 4

Проблема с рюкзаком, это может дать вам подсказку.

http://en.wikipedia.org/wiki/Knapsack_problem

Я бы сказал, что вы можете создать лямбда-выражение, содержащее фактический алогрит, но вам нужно будет использовать C #. Использование 'просто linq' будет недостаточно.

Answer 5

Я только что взломал это вместе, и я уверен, что кто-то может улучшить. Но работает ли что-то подобное?

public class App
{
    static void Main(string[] eventArgs)
    {
        var list = new[] {10, 20, 30, 40, 50};
        var whatYouNeed = GetWhatYouNeed(list, 60, 60);
        //what you need will contain 50 & 10

       //whatYouNeed = GetWhatYouNeed(list, 105,105);
        //what you need will contain (50,50, 10)
    }

    private static IList<int> _whatYouNeed = new List<int>();


    static IEnumerable<int> GetWhatYouNeed(IEnumerable<int> list, int goal, int amountRequired)
    {   //this will make sure 20 is taken over 10, if the goal is 15. highest wins
        var intYouNeed = list.OrderBy(x => Math.Abs(amountRequired - x)).FirstOrDefault(x => x > amountRequired);
        if (intYouNeed == 0) intYouNeed = list.OrderBy(x => Math.Abs(amountRequired - x)).FirstOrDefault();
        _whatYouNeed.Add(intYouNeed);

        if (_whatYouNeed.Sum() < goal)
        {
            int howMuchMoreDoYouNeed = goal - _whatYouNeed.Sum();
            GetWhatYouNeed(list, goal, howMuchMoreDoYouNeed);
        }

        return _whatYouNeed;
    }
}

Я немного ленив, передав два значения в GetWhatYouNeed, но вы поняли.

Answer 6

Это похоже на проблему Сумма подмножества , которая может быть решена за разумное количество времени для небольших наборов с использованием динамического программирования. Это не простая или распространенная проблема, поэтому вы не найдете для нее полезного метода расширения Linq:)