使用回溯法查找数字组合
本文关键字:数字 组合 查找 回溯 | 更新日期: 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;
}