帮助数学/编码一个集合的可能组合,以构成一个总数-C#

下面是一个实现,它读取芯片数量、芯片(它们的价值和数量)和buyin,并以示例格式显示结果。我已经通过评论解释了,如果你有任何问题,请告诉我。

class Test
{
    static int buyIn; 
    static int numChips;
    static List<int> chips = new List<int>(); // chips[i] = value of chips of color i
    static List<int> amountOfChips = new List<int>(); // amountOfChips[i] = number of chips of color i

    static void generateSolutions(int sum, int[] solutions, int last)
    {
        if (sum > buyIn) // our sum is too big, return
            return;

        if (sum == buyIn) // our sum is just right, print the solution
        {
            for (int i = 0; i < chips.Count; ++i)
                Console.Write("{0}/", solutions[i]);
            Console.WriteLine();

            return; // and return
        }

        for (int i = last; i < chips.Count; ++i) // try adding another chip with the same value as the one added at the last step. 
                                                 // this ensures that no duplicate solutions will be generated, since we impose an order of generation
            if (amountOfChips[i] != 0)
            {
                --amountOfChips[i]; // decrease the amount of chips
                ++solutions[i]; // increase the number of times chip i has been used

                generateSolutions(sum + chips[i], solutions, i); // recursive call

                ++amountOfChips[i]; // (one of) chip i is no longer used
                --solutions[i]; // so it's no longer part of the solution either
            }
    }

    static void Main()
    {
        Console.WriteLine("Enter the buyin:");
        buyIn = int.Parse(Console.ReadLine());
        Console.WriteLine("Enter the number of chips types:");
        numChips = int.Parse(Console.ReadLine());
        Console.WriteLine("Enter {0} chips values:", numChips);
        for (int i = 0; i < numChips; ++i)
            chips.Add(int.Parse(Console.ReadLine()));

        Console.WriteLine("Enter {0} chips amounts:", numChips);
        for (int i = 0; i < numChips; ++i)
            amountOfChips.Add(int.Parse(Console.ReadLine()));

        int[] solutions = new int[numChips];

        generateSolutions(0, solutions, 0);
    }
} 

输入buyin:
10

三
输入3个值:
1


输入3个筹码金额:
10
10
10


6/2/0/

4/3/0/
3/1/1/

1/2/1/

按芯片的种类递归地分解问题。

对于基本情况,有多少种方法可以让零筹码的X美元买入?如果X为零,有一种方法:没有筹码。如果X大于零,就没有办法了。

现在我们需要解决N种芯片的问题,给出N-1的解。我们可以拿一种芯片,把每一个可能的芯片数目都考虑进去。例如,如果芯片是2美元,而买入价是5美元,那么尝试使用其中的0、1或2个。对于每一次尝试,我们只能使用剩余的N-1个芯片来弥补剩余的值。我们可以通过递归调用来解决这个问题,然后将当前芯片添加到它返回的每个解决方案中。

private static IEnumerable<IEnumerable<Tuple<Chip, int>>> GetAllChipSuggestions(List<Chip> chips, int players, int totalValue)
{
    return GetAllChipSuggestions(chips, players, totalValue, 0);
}

private static IEnumerable<IEnumerable<Tuple<Chip, int>>> GetAllChipSuggestions(List<Chip> chips, int players, int totalValue, int firstChipIndex)
{
    if (firstChipIndex == chips.Count)
    {
        // Base case: we have no chip types remaining
        if (totalValue == 0)
        {
            // One way to make 0 with no chip types
            return new[] { Enumerable.Empty<Tuple<Chip, int>>() };
        }
        else
        {
            // No ways to make more than 0 with no chip types
            return Enumerable.Empty<IEnumerable<Tuple<Chip, int>>>();
        }
    }
    else
    {
        // Recursive case: try each possible number of this chip type
        var allSuggestions = new List<IEnumerable<Tuple<Chip, int>>>();
        var currentChip = chips[firstChipIndex];
        var maxChips = Math.Min(currentChip.TotalChipsInChipset / players, totalValue / currentChip.ChipValue);
        for (var chipCount = 0; chipCount <= maxChips; chipCount++)
        {
            var currentChipSuggestion = new[] { Tuple.Create(currentChip, chipCount) };
            var remainingValue = totalValue - currentChip.ChipValue * chipCount;
            // Get all combinations of chips after this one that make up the rest of the value
            foreach (var suggestion in GetAllChipSuggestions(chips, players, remainingValue, firstChipIndex + 1))
            {
                allSuggestions.Add(suggestion.Concat(currentChipSuggestion));
            }
        }
        return allSuggestions;
    }
}

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

还有代码链接吗?那对你有帮助。