132 lines
4.6 KiB
C#
132 lines
4.6 KiB
C#
using System;
|
|
|
|
// ReSharper disable ReturnTypeCanBeEnumerable.Global
|
|
// ReSharper disable ParameterTypeCanBeEnumerable.Local
|
|
namespace EscapeRoomEngine.Engine.Runtime.Utilities
|
|
{
|
|
/// <summary>
|
|
/// The backtrack algorithm can calculate the subset of a set of samples with the sum closest to a target value.
|
|
/// </summary>
|
|
public struct Backtrack
|
|
{
|
|
private int[] indices;
|
|
private int[] values;
|
|
private int target;
|
|
|
|
public Backtrack(int[] indices, int[] values, int target)
|
|
{
|
|
this.indices = indices;
|
|
this.values = values;
|
|
this.target = target;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Find any number of elements from the given set of indices and values with the maximum sum that doesn't exceed the target sum.
|
|
/// </summary>
|
|
/// <remarks>This function uses a backtracking approach to find the sum.</remarks>
|
|
public int[] BruteForceLower(int[] chosen = null, int pos = 0)
|
|
{
|
|
chosen ??= Array.Empty<int>();
|
|
|
|
if (Sum(chosen) > target)
|
|
{
|
|
// if the sum of the chosen values exceeds the target, return nothing
|
|
return Array.Empty<int>();
|
|
}
|
|
if (pos >= indices.Length)
|
|
{
|
|
// if we cannot add any more elements, return all chosen
|
|
return chosen;
|
|
}
|
|
|
|
// find the best indices when skipping the one at the current position
|
|
var leave = BruteForceLower(chosen, pos + 1);
|
|
// find the best indices when including the one at the current position
|
|
var next = new int[chosen.Length + 1];
|
|
for (var i = 0; i < chosen.Length; i++)
|
|
{
|
|
next[i] = chosen[i];
|
|
}
|
|
next[^1] = indices[pos];
|
|
var pick = BruteForceLower(next, pos + 1);
|
|
|
|
// return the best result
|
|
return Sum(leave) > Sum(pick) ? leave : pick;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Find any number of elements from the given set of indices and values with the minimum sum that is higher than the target sum.
|
|
/// </summary>
|
|
/// <remarks>This function uses a backtracking approach to find the sum.</remarks>
|
|
public int[] BruteForceHigher(int[] chosen = null, int pos = int.MaxValue)
|
|
{
|
|
chosen ??= indices;
|
|
if (pos == int.MaxValue)
|
|
{
|
|
pos = indices.Length - 1;
|
|
}
|
|
|
|
if (Sum(chosen) < target)
|
|
{
|
|
// if the sum of the chosen values is lower than the target, return all indices (the maximum choice)
|
|
return indices;
|
|
}
|
|
if (pos < 0)
|
|
{
|
|
// if we cannot remove any more elements, return all chosen
|
|
return chosen;
|
|
}
|
|
|
|
// find the best indices when not removing the one at the current position
|
|
var leave = BruteForceHigher(chosen, pos - 1);
|
|
// find the best indices when removing the one at the current position
|
|
var next = new int[chosen.Length - 1];
|
|
for (var i = 0; i < chosen.Length; i++)
|
|
{
|
|
if (i < pos)
|
|
{
|
|
next[i] = chosen[i];
|
|
} else if (i > pos)
|
|
{
|
|
next[i - 1] = chosen[i];
|
|
}
|
|
}
|
|
var pick = BruteForceHigher(next, pos - 1);
|
|
|
|
// return the best result
|
|
return Sum(leave) < Sum(pick) ? leave : pick;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Combine the two brute force algorithms to calculate the optimal subset.
|
|
/// </summary>
|
|
public int[] BruteForce()
|
|
{
|
|
var lower = BruteForceLower();
|
|
var higher = BruteForceHigher();
|
|
var errLower = Math.Abs(target - Sum(lower));
|
|
var errHigher = Math.Abs(target - Sum(higher));
|
|
|
|
return errLower < errHigher ? lower : higher;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Get a subset of indices where the sum of their corresponding values is closest to a target sum.
|
|
/// </summary>
|
|
public static int[] Closest(int[] indices, int[] values, int target) =>
|
|
new Backtrack(indices, values, target).BruteForce();
|
|
|
|
private int Sum(int[] chosen)
|
|
{
|
|
var sum = 0;
|
|
|
|
// ReSharper disable once LoopCanBeConvertedToQuery
|
|
foreach (var i in chosen)
|
|
{
|
|
sum += values[i];
|
|
}
|
|
|
|
return sum;
|
|
}
|
|
}
|
|
} |