使用回溯法查找数字组合

本文关键字:数字 组合 查找 回溯 | 更新日期: 2023-09-27 18:00:04

我正在C#中寻找一种回溯算法,它将从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;
}

使用回溯法查找数字组合

根据我所读的内容,这个例子是:

例如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;
    }