Найти комбинацию чисел с возвратом

Я ищу алгоритм возврата на С#, который будет искать правильные числа из List<int>, где сумма этих чисел ближе всего к X.

например: list={5,1,3,5}, X = 10 вывод должен быть (5,5) (5+5 ближе всего к 10) он не может быть (3,3,3,1), потому что я нельзя использовать номер более одного раза из List. (если у нас есть две части из числа 3, мы можем использовать два раза)

например 2: list={4,1,3,4}, X=10 вывод должен быть {4,1,3} и {1,3,4}.

У меня есть такой код для запуска, но я не могу этого сделать; (Я знаю, что есть википедия о возврате и рюкзаке, но мне это не помогает)

static void BackTrack(int lvl, bool Van, int[] E)
{
   int i = -1;
   do
   {
      i++;
      if (ft(lvl, i))
      {
         int k = 0;
         while (k < szint && fk(E[i], E[k]))
         {
            k++;
         }
         if (k == szint)
         {
            E[k] = R[lvl,i];
            if (lvl == E.Length - 1)
            {
            }
            else
            {
               BackTrack(lvl + 1, Van, E);
            }
         }
      }
   } 
   while (i < E.Length - 1);
}

static bool fk(int nr, int nr2)
{
   return (nr + nr2 <= 10);
}

static bool ft(int lvl, int nr)
{
   return true;
}

c# sum knapsack-problem backtracking
person TeddySnow    schedule 25.04.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Из того, что я читаю, этот пример:

например 2: list={4,1,3,4}, X=10 вывод должен быть {4,1,3} и {1,3,4}.

вывод должен быть {4,1,4} 9 ближе, чем 8.

Вот что я сделал. это работает с двумя примерами, которые вы привели.

public List<int> highest(List<int> list, int number)
    {
        //probably a better way to do this
        IEnumerable<int> orderedList = list.OrderByDescending(item => item);

        var currentNumber = 0;
        List<int> combinationResult = new List<int>();
        foreach (var item in orderedList)
        {
            var temp = currentNumber + item;
            if (temp <= number)
            {
                combinationResult.Add(item);
                currentNumber = temp;
            }
        }
        return combinationResult;
    }
person Delta    schedule 25.04.2014
comment
Я просто вижу, он дает правильные цифры, но мне нужно вернуться :( - person TeddySnow; 25.04.2014
comment
что вы имеете в виду под обратным ходом? - person Delta; 25.04.2014
comment
найти числа с рекурсивным алгоритмом без сортировки в списке. ссылка - person TeddySnow; 25.04.2014