Here I have the code that solves the following riddle. A farmer goes to a market with 100 bucks. He wants to spend exactly 100 bucks and exactly 100 animals to buy. Sheep cost 8 bucks, chickens cost 3 bucks, rabbits cost only 0.50 bucks each. In the code I have some of the vaild combinations printed out. The problem is now how do I make it show the total number of combinations that have been checked.
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");
}
}
}
}
}
}
Current output:
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
What the final output should look like:
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
CodePudding user response：
The number of combinations should be the number of times the if statement was checked, which is to say, the number of times the outer loop executed times the number of times the inner loop executed.
Add a counter int combinationsChecked = 0; outside of the outerloop and after the if statement in the inner loop increment this counter by one. Then, after the outer loop finishes executing print the result.
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");
CodePudding user response：
Just tally up the count and display it at the end.
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");
}
}
That being said, you can solve this problem without brute-forcing in much much shorter time. All you care about is the average cost of an animal (1$), so just combine animals intelligently until their average cost is 1$. Then multiply that combination until you've got 100 animals. Of course, your total number of animals in the combination will need to be a factor of 100. I bet you can make a 5 animal combination that works
Update: here is how I solved your problem in only 146 combinations checked. It works for any number of animals with any prices:
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;
}
}