How to solve this problem in C++?

Question

C++ / C#

#include <iostream>

int main() {
  int sum;

  std::cout << "Введите сумму, которую хотите обналичить : ";
  std::cin >> sum;

  if (sum > 150000) {
    std::cout << "Превышено максимальное число для вывода денег.";
  } else if ((sum % 5000 == 0) || ((sum - 5000) != 0)) {
    int remainder;
    remainder = sum - 5000;
    std::cout << sum / 5000 << " купюр по 5000";       //нужно как то поместить в if
  if (remainder == 0) {
    std::cout << "1 купюра по 5000";
  } else if (remainder % 2000 == 0) {
    std::cout << " и " << remainder / 2000 << " купюр по 2000";       //еще склонения купюр надо сделать
  } else if (remainder % 1000 == 0) {
    std::cout << " и " << remainder / 1000 << " купюр по 1000";
  } else if (remainder % 500 == 0) {
    std::cout << " и " << remainder / 500 << " купюр по 500";
  } else if (remainder % 200 == 0) {
    std::cout << " и " << remainder / 200 << " купюр по 200";
  } else if (remainder % 100 == 0) {
    std::cout << " и " << remainder / 100 << " купюр по 100";
  }

  }/* else if ((sum % 2000 == 0) || ((sum - 2000) != 0)) {
    int remainder = sum - 2000;
    //std::cout << sum / 2000  << " купюр по 2000";
    if (remainder == 0) {
      std::cout << "1 купюра по 2000";
    }
    else if (remainder % 1000 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 1000 << " купюр по 1000";
  } else if (remainder % 500 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 500 << " купюр по 500";
  } else if (remainder % 200 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 200 << " купюр по 200";
  } else if (remainder % 100 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 100 << " купюр по 100";
  }
  }

   else if ((sum % 1000 == 0) && ((sum - 1000) != 0)) {
    int remainder = sum - 1000;
    std::cout << sum / 1000  << " купюр по 1000";
    if (remainder % 500 == 0) {
    std::cout << " и " << remainder / 500 << " купюр по 500";
  } else if (remainder % 200 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 200 << " купюр по 200";
  } else if (remainder % 100 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 100 << " купюр по 100";
  }
  }

  else if ((sum % 500 == 0) && ((sum - 500) != 0)) {
    int remainder = sum - 500;
    std::cout << sum / 500  << " купюр по 500";
    if (remainder % 200 == 0) {
    std::cout << " и " << remainder / 200 << " купюр по 200";
  } else if (remainder % 100 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 100 << " купюр по 100";
  }
  }

  else if ((sum % 200 == 0) && ((sum - 200) != 0)) {
    int remainder = sum - 200;
    std::cout << sum / 200  << " купюр по 200";
    if (remainder % 100 == 0 && remainder != 0) {
    std::cout << " и " << remainder / 100 << " купюр по 100";
  }
  }

  else if ((sum % 100 == 0) && ((sum - 100) != 0)) {
    int remainder = sum - 100;
    std::cout << sum / 100  << " купюр по 100";
  } else {
    std::cout << "Такую сумму вывести невозможно";
  }*/
}

I don't know how to solve. algorithm with bent logic. Any help will be glad

text of the problem:
One day Vasya went to an ATM and wanted to cash out N rubles. The ATM has banknotes in denominations of 100, 200, 500, 1000, 2000 and 5000 rubles. The ATM wants to give Vasya the requested amount, using as few banknotes as possible.

Write a program for an ATM that, given the number N, decides how many banknotes of each denomination must be dispensed to receive the amount of exactly N rubles, or says that it is impossible to dispense exactly N rubles (for example, if N is not divisible by 100). As an additional limitation, please note that the ATM cannot dispense more than 150,000 rubles at a time, an error message should be displayed when trying to request such an amount.

If it is possible to issue the requested amount in different ways that do not differ in the total number of banknotes, it is allowed to withdraw any of them. For example, 800 rubles can be given out as 4 for 200 or as 500 and 3 more for 100.

Answer 1

Having sorted out different amounts a little with your hands, you can understand that a greedy solution works here - you can take the largest bill that fits into the remaining amount.
This can also be proven. It makes no sense to take more than one 100, they could be replaced by 200. It also makes no sense to take more than two 200 - three can be exchanged for 500 + 100, which is less than bills. Similarly for all remaining banknotes.
Well, it remains for you to check for each bill that the remaining amount is not less than the bill, then give out how many bills fit and replace the amount with the remainder of the division.