Découvrez les combinaisons de nombres d'un ensemble d'ajouter jusqu'à un total de

Version C#

configuration de test:

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main(string[] args)
    {
    //subtotal list
    List<double> totals = new List<double>(new double[] { 1, -1, 18, 23, 3.50, 8, 70, 99.50, 87, 22, 4, 4, 100.50, 120, 27, 101.50, 100.50 });

    //get matches
    List<double[]> results = Knapsack.MatchTotal(100.50, totals);

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

    Console.WriteLine("Done.");
    Console.ReadKey();
    }
}

code:

using System.Collections.Generic;
using System.Linq;

public class Knapsack
{
    internal static List<double[]> MatchTotal(double theTotal, List<double> subTotals)
    {
    List<double[]> results = new List<double[]>();

    while (subTotals.Contains(theTotal))
    {
        results.Add(new double[1] { theTotal });
        subTotals.Remove(theTotal);
    }

    //if no subtotals were passed
    //or all matched the Total
    //return
    if (subTotals.Count == 0)
        return results;

    subTotals.Sort();

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

    //if there aren't any negative values
    //we can remove any values bigger than the total
    if (mostNegativeNumber == 0)
        subTotals.RemoveAll(d => d > theTotal);

    //if there aren't any negative values
    //and sum is less than the total no need to look further
    if (mostNegativeNumber == 0 && subTotals.Sum() < theTotal)
        return results;

    //get the combinations for the remaining subTotals
    //skip 1 since we already removed subTotals that match
    for (int choose = 2; choose <= subTotals.Count; choose++)
    {
        //get combinations for each length
        IEnumerable<IEnumerable<double>> combos = Combination.Combinations(subTotals.AsEnumerable(), choose);

        //add combinations where the sum mathces the total to the result list
        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 ?                        //if choose = 0
        new[] { new T[0] } :                    //return empty Type array
        elements.SelectMany((element, i) =>     //else recursively iterate over array to create combinations
        elements.Skip(i + 1).Combinations(choose - 1).Select(combo => (new[] { element }).Concat(combo)));
    }
}

résultats:

100.5
100.5
-1,101.5
1,99.5
3.5,27,70
3.5,4,23,70
3.5,4,23,70
-1,1,3.5,27,70
1,3.5,4,22,70
1,3.5,4,22,70
1,3.5,8,18,70
-1,1,3.5,4,23,70
-1,1,3.5,4,23,70
1,3.5,4,4,18,70
-1,3.5,8,18,22,23,27
-1,3.5,4,4,18,22,23,27
Done.

Si les sous-totaux sont répétées, il n'y aura semblent être les résultats (l'effet désiré). En réalité, vous aurez probablement besoin d'utiliser la sous-total Tupled avec une pièce d'identité, de sorte que vous pouvez rapporter à vos données.

OriginalL'auteur Dan

Il y a un bon marché Excel Add-in qui permet de résoudre ce problème: SumMatch

OriginalL'auteur Albert

Son genre de sac à Dos 0-1 problème est NP-complet et peut être résolu par programmation dynamique en temps polynomial.

http://en.wikipedia.org/wiki/Knapsack_problem

Mais à la fin de l'algorithme, vous devez également vérifier que la somme est ce que tu voulais.

OriginalL'auteur vinothkr

Pas une super solution efficace mais heres une mise en œuvre en coffeescript

combinations retourne toutes les combinaisons possibles des éléments dans list

combinations = (list) ->
        permuations = Math.pow(2, list.length) - 1
        out = []
        combinations = []

        while permuations
            out = []

            for i in [0..list.length]
                y = ( 1 << i )
                if( y & permuations and (y isnt permuations))
                    out.push(list[i])

            if out.length <= list.length and out.length > 0
                combinations.push(out)

            permuations--

        return combinations

et puis find_components l'utilise pour déterminer le nombre d'ajouter jusqu'à total

find_components = (total, list) ->
    # given a list that is assumed to have only unique elements

        list_combinations = combinations(list)

        for combination in list_combinations
            sum = 0
            for number in combination
                sum += number

            if sum is total
                return combination
        return []

Heres un exemple

list = [7.2, 3.3, 4.5, 6.0, 2, 4.1]
total = 7.2 + 2 + 4.1

console.log(find_components(total, list)) 

qui renvoie [ 7.2, 2, 4.1 ]

OriginalL'auteur Loourr