0 
 Length = input Long(can be 2550, 2880, 2568, etc)
 List<long> = {618, 350, 308, 300, 250, 232, 200, 128}

该程序需要一个长值，对于那个特定的长值，我们必须从上面的列表中找到可能的组合，添加后会给我一个输入结果（相同的值可以使用两次）。可能存在 +/- 30 的差异。

必须使用最大的数字。

例如：长度 = 868 对于这种组合可以

组合 1 = 618 + 250

组合2 = 308 + 232 + 200 +128

正确的组合是组合 1

但也应该有不同的组合。

public static void Main(string[] args)
    {
        //subtotal list
        List<int> totals = new List<int>(new int[] { 618, 350, 308, 300, 250, 232, 200, 128 });

        // get matches
        List<int[]> results = KnapSack.MatchTotal(2682, totals);

        // print results
        foreach (var result in results)
        {
            Console.WriteLine(string.Join(",", result));
        }

        Console.WriteLine("Done.");            
    }

internal static List<int[]> MatchTotal(int theTotal, List<int> subTotals)
    {
        List<int[]> results = new List<int[]>();
        while (subTotals.Contains(theTotal))
        {
            results.Add(new int[1] { theTotal });
            subTotals.Remove(theTotal);
        }

        if (subTotals.Count == 0)
            return results;

        subTotals.Sort();

        double mostNegativeNumber = subTotals[0];
        if (mostNegativeNumber > 0)
            mostNegativeNumber = 0;

        if (mostNegativeNumber == 0)
            subTotals.RemoveAll(d => d > theTotal);

        for (int choose = 0; choose <= subTotals.Count; choose++)
        {
            IEnumerable<IEnumerable<int>> combos = Combination.Combinations(subTotals.AsEnumerable(), choose);

            results.AddRange(from combo in combos where combo.Sum() == theTotal select combo.ToArray());
        }
        return results;
    }


public static class Combination
{
        public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int choose)
        {
            return choose == 0 ?
                new[] { new T[0] } :
                elements.SelectMany((element, i) =>
                    elements.Skip(i + 1).Combinations(choose - 1).Select(combo => (new[] { element }).Concat(combo)));
        }
}

我已经使用了上面的代码，它可以更简化吗，在这里我也得到了唯一的值。一个值可以使用任意次数。但最大的数字必须被给予最高优先级。

我有一个验证来检查总和是否大于输入值。即使在那里逻辑也失败了..

4

2 回答 2

0

您显示的算法假定列表按升序排序。如果不是，那么您首先必须在 O(nlogn) 时间内对列表进行排序，然后执行算法。

此外，它假设您只考虑配对组合并且您在第一场比赛中退出。如果要查找所有组合，则不要使用“break”，而只需输出组合并增加 startIndex 或减少 endIndex。

此外，您应该检查范围（targetSum - 30 到 targetSum + 30），而不仅仅是确切的值，因为问题表明允许有误差范围。

在我看来，这是最好的解决方案，因为它的复杂性是 O(nlogn + n)，包括排序。

于 2013-10-25T06:44:32.907 回答
0

V4 - 递归方法，使用堆栈结构而不是线程上的堆栈帧

它可以工作（在 VS 中测试），但可能存在一些错误。

    static int Threshold = 30;
    private static Stack<long> RecursiveMethod(long target)
    {
        Stack<long> Combination = new Stack<long>(establishedValues.Count); //Can grow bigger, as big as (target / min(establishedValues)) values
        Stack<int> Index = new Stack<int>(establishedValues.Count); //Can grow bigger
        int lowerBound = 0;
        int dimensionIndex = lowerBound;
        long fail = -1 * Threshold;
        while (true)
        {
            long thisVal = establishedValues[dimensionIndex];
            dimensionIndex++;
            long afterApplied = target - thisVal;

            if (afterApplied < fail)
                lowerBound = dimensionIndex;
            else
            {
                target = afterApplied;
                Combination.Push(thisVal);
                if (target <= Threshold)
                    return Combination;
                Index.Push(dimensionIndex);
                dimensionIndex = lowerBound;
            }

            if (dimensionIndex >= establishedValues.Count)
            {
                if (Index.Count == 0)
                    return null; //No possible combinations

                dimensionIndex = Index.Pop();
                lowerBound = dimensionIndex;
                target += Combination.Pop();
            }
        }

    }

Maybe V3 - 尝试每种组合的有序解决方案的建议

尽管没有选择这作为相关问题的答案，但我相信这是一个很好的方法 - https://stackoverflow.com/a/17258033/887092（否则您可以尝试选择的答案（尽管输出仅对集合中的 2 个项目求和，而不是最多 n 个项目））-它将枚举每个选项，包括相同值的倍数。V2 可以工作，但效率会略低于有序解决方案，因为可能会多次尝试相同的失败尝试。

V2 - 随机选择 - 将能够重复使用相同的数字两次

我喜欢使用随机数作为“智能”，允许计算机暴力破解解决方案。它也很容易分发——例如，同时尝试的两个线程之间没有状态依赖性。

static int Threshold = 30;

    public static List<long> RandomMethod(long Target)
    {
        List<long> Combinations = new List<long>();
        Random rnd = new Random();

        //Assuming establishedValues is sorted
        int LowerBound = 0;
        long runningSum = Target;

        while (true)
        {
            int newLowerBound = FindLowerBound(LowerBound, runningSum);

            if (newLowerBound == -1)
            {
                //No more beneficial values to work with, reset
                runningSum = Target;
                Combinations.Clear();
                LowerBound = 0;
                continue;
            }


            LowerBound = newLowerBound;

            int rIndex = rnd.Next(LowerBound, establishedValues.Count);
            long val = establishedValues[rIndex];
            runningSum -= val;
            Combinations.Add(val);

            if (Math.Abs(runningSum) <= 30)
                return Combinations;
        }
    }

    static int FindLowerBound(int currentLowerBound, long runningSum)
    {
        //Adjust lower bound, so we're not randomly trying a number that's too high
        for (int i = currentLowerBound; i < establishedValues.Count; i++)
        {
            //Factor in the threshold, because an end aggregate which exceeds by 20 is better than underperforming by 21.
            if ((establishedValues[i] - Threshold) < runningSum)
            {
                return i;

            }
        }
        return -1;
    }

V1 - 有序选择 - 不能重复使用相同的号码两次

  1. 添加这个非常方便的扩展函数（使用二进制算法查找所有组合）：

    //Make sure you put this in a static class inside System namespace
public static IEnumerable<List<T>> EachCombination<T>(this List<T> allValues)
{
    var collection = new List<List<T>>();
    for (int counter = 0; counter < (1 << allValues.Count); ++counter)
    {
        List<T> combination = new List<T>();
        for (int i = 0; i < allValues.Count; ++i)
        {
            if ((counter & (1 << i)) == 0)
                combination.Add(allValues[i]);
        }

        if (combination.Count == 0)
            continue;

        yield return combination;
    }
}

  2. 使用功能

     static List<long> establishedValues = new List<long>() {618, 350, 308, 300, 250, 232, 200, 128, 180, 118, 155};

 //Return is a list of the values which sum to equal the target. Null if not found.         
 List<long> FindFirstCombination(long target)
 {
     foreach (var combination in establishedValues.EachCombination())
     {
       //if (combination.Sum() == target)
           if (Math.Abs(combination.Sum() - target) <= 30) //Plus or minus tolerance for difference
          return combination;
     }

     return null; //Or you could throw an exception
 }

  3. 测试解决方案

    var target = 858;
var result = FindFirstCombination(target);
bool success = (result != null && result.Sum() == target);

//TODO: for loop with random selection of numbers from the establishedValues, Sum and test through FindFirstCombination
于 2013-10-25T07:16:22.957 回答