优化子集选择算法,在偏差范围内比较解决方案
本文关键字:范围内 比较 解决方案 子集 选择 算法 优化 | 更新日期: 2023-09-27 17:53:58
我目前正在使用一种算法来查找元素(无符号小数),其中和最接近指定值target
。编辑:元素只能使用一次。
private class Solution
{
public int StartIndex;
public int EndIndex;
public decimal Sum;
public int Length
{
get { return EndIndex - StartIndex + 1; }
}
}
public static List<decimal> Solve(List<decimal> elements, decimal target)
{
Solution bestSolution = new Solution { StartIndex = 0, EndIndex = -1, Sum = 0 };
decimal bestError = Math.Abs(target);
Solution currentSolution = new Solution { StartIndex = 0, Sum = 0 };
for (int i = 0; i < elements.Count; i++)
{
currentSolution.EndIndex = i;
currentSolution.Sum += elements[i];
while (elements[currentSolution.StartIndex] <= currentSolution.Sum - target)
{
currentSolution.Sum -= elements[currentSolution.StartIndex];
++currentSolution.StartIndex;
}
decimal currentError = Math.Abs(currentSolution.Sum - target);
if (currentError < bestError || currentError == bestError && currentSolution.Length < bestSolution.Length)
{
bestError = currentError;
bestSolution.Sum = currentSolution.Sum;
bestSolution.StartIndex = currentSolution.StartIndex;
bestSolution.EndIndex = currentSolution.EndIndex;
}
}
return elements.GetRange(bestSolution.StartIndex, bestSolution.Length);
}
存在多个解,我需要得到元素较少的解。我一直在分析代码,但不能断定是不是这样。
更好,但可能更难完成的是选择一个范围内元素较少的解。
,
Target value = 50.00
Solution A: 4 elements => 50.00
Solution B: 3 elements => 49.99
solution C: 2 element => 49.90 ««« PREFERABLE (Less elements within a given 0.50 deviation )
Solution D: 1 elements => 49.30
我正在寻找如何优化这个算法来完成上面的更改的帮助。谢谢!
尝试递归算法。级别0的代码尝试10,20,30,40。在第二级尝试了两个数字,比如10,20,10,30,10,40。该代码有一个特性,当在某个级别上的和大于目标时停止尝试。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
List<decimal> inputs = new List<decimal> { 10, 20, 30, 40 };
int startIndex = 0;
decimal target = 50;
Solution solution = new Solution(inputs);
List<decimal> elements = new List<decimal>();
solution.Solve(elements, target, startIndex);
}
public class Solution
{
private List<decimal> inputs = null;
private static bool first = true;
public static decimal Sum = -1;
public static decimal error = -1;
public static List<decimal> elements { get; set; }
public Solution(List<decimal> inputs)
{
elements = new List<decimal>();
this.inputs = new List<decimal>(inputs);
this.inputs.Sort();
}
public static bool BestSolution(List<decimal> newSolution, decimal target)
{
bool higher = false;
if(first == true)
{
AddSolution(newSolution, target);
first = false;
}
else
{
decimal newError = Math.Abs(newSolution.Sum() - target);
if(newError < error)
{
AddSolution(newSolution, target);
}
else
{
if((newError == error) && (newSolution.Count < elements.Count))
{
AddSolution(newSolution, target);
}
}
}
if(elements.Sum() >= target) higher = true;
return higher;
}
private static void AddSolution(List<decimal> newSolution, decimal target)
{
Sum = newSolution.Sum();
error = Math.Abs(newSolution.Sum() - target);
elements = new List<decimal>(newSolution);
}
public void Solve(List<decimal> localElements, decimal target, int startIndex)
{
for (int i = startIndex; i < inputs.Count; i++)
{
List<decimal> newElements = new List<decimal>(localElements);
newElements.Add(inputs[i]);
bool higher = Solution.BestSolution(newElements, target);
if (!higher)
{
Solve(newElements, target, i + 1);
}
else
{
break;
}
}
}
}
}
}