How to use the minimum possible combination of a coin change problem using recursive in C #

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

// Do not modify change
class Change
{
 public long coin2 = 0;
 public long bill5 = 0;
 public long bill10 = 0;
}

class Solution
{

 // Do not modify method signature
 public static Change OptimalChange(long s)
 {
 Change _change = new Change();
 //To implement here
 return _change;
 }

 public static int GetCombinations(int total, int index, int[] list, List cur)
 {
 if (total == 0)
 {
 foreach (var i in cur)
 {
 Console.Write(i + "");< br /> }
 Console.WriteLine();
 return 1;
 }
 if (index == list.Length)
 {
 return 0;
 }
 int ret = 0;
 for (; total >= 0; total -= list[index])
 {
 ret += GetCombinations(total, index + 1, list, cur);
 cur.Add( list[index]);

 }
 for (int i = 0; i  {
 while (cur.Count > i && cur[i] == list[index])
 {
 cur.RemoveAt(i);
 }
 }
 return ret;
 }

}

public class Program
{
 public static void Main()
 {
 Console.WriteLine( "Hello Change");
 int s = 41;
 /*Change m = Solution.OptimalChange(s);
 Console.WriteLine("Coins(s) 2euros :" + m. coin2);
 Console.WriteLine("Bill(s) 5euors :" + m.bill5);
 Console.WriteLine("Bill(s) 10eu ors :" + m.bill10);

 long result = m.coin2*2 + m.bill5*5 + m.bill10*10;

 Console.WriteLine( "
Change given =", + result);*/
 Solution sol = new Solution();
 int[] l = {
 2,
 5,
 10
 };
 Solution.GetCombinations(s, 0, l, new List());
 }
}

// Do not modify change
class Change
{
 public long coin2 = 0;
 p ublic long bill5 = 0;
 public long bill10 = 0;
}

sealed class Change
{
 public long Two {get; }
 public long Five {get; }
 public long Ten {get; }
 public Change(long two, long five, long ten)
 {
 this.Two = two;
 this.Five = five;
 this.Ten = ten;
 }
 public Change AddTwo() => new Change(Two + 1, Five, Ten);
 public Change AddFive() => new Change(Two, Five + 1, Ten);
 public Change AddTen() => new Change(Two, Five, Ten + 1);
 public long Count => Two + Five + Ten;
 public long Total => Two * 2 + Five * 5 + Ten * 10;
}

public static Change OptimalChange(long s)
{
 // Are we in the base case? Solve the problem.
 // If not, break it down into a smaller problem.
}

public static Change OptimalChange(long s)
{
 if (s <0) 
 return null;
 if (s == 0) 
 return new Change(0, 0, 0);

public static Change OptimalChange(long s)
{
 if (s <0) 
 return null;
 if (s == 0) 
 return new Change(0, 0, 0); Change tryTen = OptimalChange(s-10)?.AddTen(); .. .

I am new to C# and I have a recursion problem to solve I want to get the minimum number of coins in this coin replacement problem. I have adjusted the algorithm for it, but I need to return an object of type Change, which will contain the smallest possible combination.

< p>I am trying to implement an algorithm, but I have all possible combinations.

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

// Do not modify change
class Change
{
 public long coin2 = 0;
 public long bill5 = 0;
 public long bill10 = 0;
}

class Solution
{

 // Do not modify method signature
 public static Change OptimalChange(long s)
 {
 Change _change = new Change();
 //To implement here
 return _change;
 }

 public static int GetCombinations(int total, int index, int[] list, List cur)
 {
 if (total == 0)
 {
 foreach ( var i in cur)
 {
 Console.Write(i + "");
 }
 Console.WriteLine();
 return 1;
 }
 if (index == list.Length) 
 {
 return 0;
 }
 int ret = 0;
 for (; total >= 0; total -= list[index])
 {
 ret += GetCombinations(total, index + 1, list, cur);
 cur.Add(list[index]);

 }
 for ( int i = 0; i  {
 while (cur.Count> i && cur[i] == list[index])
 {
 cur.RemoveAt(i);
 }
 }
 return ret;
 }

}

public class Program
{
 public static void Main()
 {
 Console.WriteLine("Hello Change");
 int s = 41;
 /* Change m = Solution.OptimalChange(s);
 Console.WriteLine("Coins(s) 2euros :" + m.coin2);
 Console.WriteLine("Bill(s) 5euors :" + m.bill5);
 Console.WriteLine("Bill(s) 10euors :" + m.bill10);

 long result = m.coin2*2 + m.bill5*5 + m.bill10*10;

 Console.WriteLine("
Change given =", + result);*/
 Solution sol = new Solution();
 int[] l = {
 2,
 5,
 10
 };
 Solution.GetCombinations(s, 0 , l, new List());
 }
}

Expected result

Example: Available coins are {2,5,10 }

– I entered 12 –

The plan should return

Coin 2 Euro: 1
Bill 5 people: 0
Bill( s)10euors: 1

– I entered 17 –

The plan should return

Coin 2 Euro: 1
Bill 5 people: 1< br>Bill(s)10euors: 1

First, understand the basic concept of recursion:

>If we The problem can be solved without recursion, please solve it and return the solution.
>If we can’t, then reduce the problem to one or more smaller problems, recursively solve each smaller problem, Combine solutions to solve bigger problems.

Secondly, understand what the basic idea of ​​dynamic programming is:

>Recursive solutions often recalculate the same problem multiple times; storage The solution is sometimes more effective than recalculating it.

Well, let us solve your problem.

// Do not modify change
class Change
{
 pub lic long coin2 = 0;
 public long bill5 = 0;
 public long bill10 = 0;
}

Pish tosh. This class is terrible. Fix it !

sealed class Change
{
 public long Two {get; }
 public long Five {get; }
 public long Ten {get; }
 public Change(long two, long five, long ten)
 {
 this.Two = two;
 this.Five = five;
 this.Ten = ten;
 }
 public Change AddTwo() => new Change(Two + 1, Five, Ten);
 public Change AddFive() => new Change(Two, Five + 1, Ten);
 public Change AddTen() => new Change(Two, Five, Ten + 1);
 public long Count => Two + Five + Ten;
 public long Total => Two * 2 + Five * 5 + Ten * 10;
}

Start with a data structure that can help you, not a data structure that hurts you.

Now, let us write a recursive function:

public static Change OptimalChange(long s)
{
 // Are we in the base case? Solve the problem.
 // If not, break it down into a smaller problem.
}

What is the basic case? There are actually two. If the sum is negative, there is no solution, if the sum is zero, there is a zero solution.

public static Change OptimalChange(long s)
{
 if (s <0) 
 return null;
 if (s == 0) 
 return new Change(0, 0, 0);

< p>Well, it’s easy. What’s the difficult part? Well, if there is one solution, then it has two, or it has five, or it has ten, right? Or maybe all three. So let’s find out.

public static Change OptimalChange(long s)
{
 if (s <0) 
 return null;
 if (s == 0) 
 return new Change(0, 0, 0); Change tryTen = OptimalChange(s-10)?.AddTen(); .. .

Can you take it from here?

When you have the data structure to implement the required operations, how easy it is to see the problem? Again, always create a data structure that can help you.

Next question: The algorithm is very inefficient. Why? Because we are constantly redoing the problems we have already done. Suppose we are evaluating OptimalChange(22). This is called OptimalChange(12), it calls OptimalChange(7), and it calls OptimalChange(5). But OptionalChange(12) also calls OptimalChange(10), it calls OptimalChange(5) again. The answer has not changed, but we do the calculation again.

So what should we do? We use dynamic programming technology. There are two ways to do it:

>Continue recursively and remember the recursive function.
>Create a change array and fill it out at any time.

But wait, there are more problems than performance problems. We minimize the problem 10 times, at least 2 times each time, but the parameters are very long; it may be billions or trillions. If we have a recursive solution, We will hit the stack, if we have an array-based solution, it is too big.

Within the given range of possible inputs, we need to solve this problem smarter. Think about it; we Can the problem be solved analytically, without recursion, arrays or long-running loops? Or, equivalently, is there a way to quickly reduce the big problems of the smallest problems? Then you can solve small problems through dynamic programming.

Just like homework problems, remember that you are bound by good academic rules. If you use SO ideas in homework solutions, you must give trust .Failing to do so is plagiarism, and if you persist, you will be expelled from a decent school.