I ask for help in the question:

There are elements: 30, 70, 90, 100.

There is an amount that the user enters.

If the user enters 60 , this amount does not change

If the user enters 45 -> amount 60

155->160(30+70+30+30)

150->150(90+30+30)

etc.

Elements within the sum can be used any number of times.

Prompt fast algorithm to do this.

  • Personally, I do not understand, try to describe in more detail. What is multiplicity? The sum of what? - cpp questions
  • there is an input field, in which the least multiplicity is 30 (if the user presses up, the amount becomes 60)
  • and if 80 enters then how to be? or 95? - Drakonoved
  • And why 160, but not 150 (30 + 30 + 30 + 30 + 30)? Describe the algorithm in more detail - Andrew NOP
  • one
    @Rabin, look at the question of whether I didn’t distort anything with my editing - Andrey NOP

2 answers 2

This task is one of the subsets of subset sum or coin change - how to pay with coins from a given set with a possible excess.

It is solved by dynamic programming - for example, you can create an array of length sum + наименьшая монета , fill it with possible layouts and see which first cell is full, starting with cell sum .

    Not the fastest, but rather simple recursive algorithm (C # code). You need to start with something?

     static int GetSum(int value, int[] nominals) { if (value <= 0) return 0; int res = nominals[0] + GetSum(value - nominals[0], nominals); for (int i = 1; i < nominals.Length; ++i) { int candidat = nominals[i] + GetSum(value - nominals[i], nominals); if (res > candidat) res = candidat; } return res; }

    Test:

     int[] nominals = { 30, 70, 90, 100 }; Console.WriteLine(GetSum(45, nominals)); // 60 Console.WriteLine(GetSum(60, nominals)); // 60 Console.WriteLine(GetSum(155, nominals)); // 160 Console.WriteLine(GetSum(150, nominals)); // 150

    If you add a memo:

     static Dictionary<int, int> mem = new Dictionary<int, int>(); static int GetSum(int value, int[] nominals) { if (value <= 0) return 0; if (mem.TryGetValue(value, out var res)) return res; res = nominals[0] + GetSum(value - nominals[0], nominals); for (int i = 1; i < nominals.Length; ++i) { int candidat = nominals[i] + GetSum(value - nominals[i], nominals); if (res > candidat) res = candidat; } return mem[value] = res; }

    then it takes such numbers as input:

     Console.WriteLine(GetSum(54321, nominals)); // 54330