如何在我的代码中添加组合总数？ C＃

Question

这里我有解决以下谜语的代码。一个农民带着 100 美元去市场。他想恰好花 100 美元和恰好 100 只动物来购买。羊8块钱，鸡3块钱，兔子只要0.50块钱一只。在代码中，我打印了一些有效的组合。现在的问题是如何让它显示已检查的组合总数。

using System;


    namespace riddle
    {
    class Program
    {

    static void Main(string[] args)
    {
        int priceSheep = 8;
        int priceChicken = 3;
        float priceRabbit = 0.5F;

        for (int i = 0; i <= 100 / priceSheep; ++i)
        {
            for (int j = 0; j <= ((100 - i * priceSheep) / priceChicken); ++j)
            {
                int money = (100 - priceSheep * i - priceChicken * j);
                if (priceRabbit * (100 - i - j) == money)
                {
                    Console.WriteLine(i + " " + "sheeps" + " " + j + " " + "chickens" + " " + (100 - i - j) + " " + "rabbits");
                }
            }
        }

      }
   }
 }

当前输出：

0 sheeps 20 chickens 80 rabbits
1 sheeps 17 chickens 82 rabbits
2 sheeps 14 chickens 84 rabbits
3 sheeps 11 chickens 86 rabbits
4 sheeps 8 chickens 88 rabbits
5 sheeps 5 chickens 90 rabbits
6 sheeps 2 chickens 92 rabbits

最终输出应该是这样的：

0 sheeps 20 chickens 80 rabbits
1 sheeps 17 chickens 82 rabbits
2 sheeps 14 chickens 84 rabbits
3 sheeps 11 chickens 86 rabbits
4 sheeps 8 chickens 88 rabbits
5 sheeps 5 chickens 90 rabbits
6 sheeps 2 chickens 92 rabbits
1030301 combinations checked

Answer 1

只需计算计数并在最后显示。

class Program
{

    static void Main(string[] args)
    {
        const int priceSheep = 8;
        const int priceChicken = 3;
        const float priceRabbit = 0.5F;
        int combinationsChecked = 0;

        for (int i = 0; i <= 100 / priceSheep; ++i)
        {
            for (int j = 0; j <= ((100 - i * priceSheep) / priceChicken); ++j)
            {
                int money = (100 - priceSheep * i - priceChicken * j);
                if (priceRabbit * (100 - i - j) == money)
                {
                    Console.WriteLine(i + " " + "sheeps" + " " + j + " " + "chickens" + " " + (100 - i - j) + " " + "rabbits");
                }

                combinationsChecked++;
            }
        }

        Console.WriteLine($"{combinationsChecked} combinations checked");

    }
}

也就是说，你可以在更短的时间内解决这个问题而无需暴力破解。你只关心一只动物的平均成本（1 美元），所以只需巧妙地组合动物，直到它们的平均成本为 1 美元。然后乘以这个组合，直到你有 100 只动物。当然，组合中的动物总数需要是 100 的因数。我打赌你可以做出 5 只动物的组合

更新：以下是我仅检查了 146 种组合就解决了您的问题的方法。它适用于任意数量的任意价格的动物：

internal class AnimalCosts
{
    public static Dictionary<string, int> GetOptimalAnimalCounts(decimal totalDollars, int totalAnimals,
        List<(string name, decimal cost)> animals, out int combinationsChecked)
    {
        combinationsChecked = 0;
        var averageCost = totalDollars/totalAnimals;
        var factors = Factor(totalAnimals);
        factors.Sort();
        var costs = animals.Select(a => a.cost).ToList();
        foreach (var animalsInCombination in factors)
        {
            var combination = new int[animalsInCombination];
            if (FindCombination(combination, 0, costs, averageCost * animalsInCombination, out var optimalCombination,ref combinationsChecked))
            {
                var dictionary = new Dictionary<string, int>();
                var multiplier = totalAnimals / animalsInCombination;
                foreach (var index in optimalCombination)
                {
                    var animalName = animals[index].name;
                    if (!dictionary.TryGetValue(animalName, out var count))
                    {
                        count = 0;
                    }

                    count += multiplier;
                    dictionary[animalName] = count;
                }

                return dictionary;
            }
        }

        return null;
    }
    static bool FindCombination(int[] currentCombination, int index, List<decimal> costs, decimal targetSum, out int[] combination, ref int combinationsChecked)
    {
        combinationsChecked++;
        if (index >= currentCombination.Length)
        {
            var sum = currentCombination.Select(item => costs[item]).Sum();
            combination = currentCombination;
            return sum == targetSum;
        }
        else
        {
            for (int i = 0; i < costs.Count; i++)
            {
                currentCombination[index] = i;
                if (FindCombination(currentCombination, index + 1, costs, targetSum,
                        out combination, ref combinationsChecked)) return true;
            }

            combination = currentCombination;
            return false;

        }
    }
    


    static List<int> Factor(int number)
    {
        var factors = new List<int>();
        int max = (int)Math.Sqrt(number);  // Round down

        for (int factor = 1; factor <= max; ++factor) // Test from 1 to the square root, or the int below it, inclusive.
        {
            if (number % factor == 0)
            {
                factors.Add(factor);
                if (factor != number / factor) // Don't add the square root twice!  Thanks Jon
                    factors.Add(number / factor);
            }
        }
        return factors;
    }
}

Answer 2

组合数应该是if语句被检查的次数，也就是外循环执行的次数乘以内循环执行的次数。

在外循环外添加一个计数器int combinationsChecked = 0;，在内循环中的if语句之后将这个计数器加1。然后，在外层循环执行完毕后打印结果。

int combinationsChecked = 0;
for (int i = 0; i <= 100 / priceSheep; ++i)
{
    for (int j = 0; j <= ((100 - i * priceSheep) / priceChicken); ++j)
    {
        int money = (100 - priceSheep * i - priceChicken * j);
        if (priceRabbit * (100 - i - j) == money)
        {
            Console.WriteLine(i + " " + "sheeps" + " " + j + " " + "chickens" + " " + (100 - i - j) + " " + "rabbits");
        }
        combinationsChecked++;
    }
}
Console.WriteLine($"{combinationsChecked} combinations checked");

如何在我的代码中添加组合总数？ C＃

How to add total number of combinations in my code? C#

c#

for-loop

if-statement

nested-loops