How to get the desired number, which is obtained as a result of adding numbers from the specified array?

Question

Algorithms

Let's say we have an array of numbers. A number is given and it is necessary to represent this number as the sum of numbers from this array.
For example:
A=[2,3,5,5,7]
If B=10 then one of the ways is 2+3+5, or 5+5 more
if B=6, then there is no solution
Limitations:
1. Numbers in the array 2 can be repeated
. One number from the array cannot be used more than 1 time. Those. if you need to get 15, then I can’t get 5 + 5 + 5 like that, because only two fives.
Addendum:
I know what numbers can appear in the array. These are: 1, 2, 5, 10, 50, 100, 500, 1000, 5000. There cannot be others.
In other words, the task sounds like this: I have banknotes of different denominations, and I need to buy goods in the store without change. Can I do it?

Answer 1

In your example, each of the numbers except 5 is divisible by the previous one. Therefore, up to a certain point - until you have to pay at least 10 rubles, and there are bills of at least 10 in your wallet - you can use the "greedy" algorithm - take the largest bill, which is less than the rest of the cost of the goods.
Let's say that only coins of 1.2.5 rubles are left. If there is at least one coin of 1 ruble, then it is safe to pay with a five-ruble coin, even if an odd price remains, then it will be possible to collect it in rubles and kopeck pieces. If there are two coins of 5 rubles each, and you have to pay at least 10 rubles, feel free to spend one of them. Wait for the second one, it can be dangerous.
In the end, you will be left with only five coins and kopeck pieces, and either no more than one nickel, or you have to pay less than a dozen. See. If you have to pay an odd amount: if there are no patches or you have to pay 1 or 3 rubles, the problem is unsolvable. Otherwise, spend a nickel, an even amount remains.
Trying to score the remainder in twos. If they are enough, you win. If not, then you have slipped an unsolvable example...
If the set of bills and coins was from the times of the USSR (1,2,3,5,10,15,20,50,100,300,500,1000,2500,5000,10000), the task would be much more difficult and interesting.
UPD. My decision is wrong. Who will find a counterexample?
More correct option.
- if there is at least one coin of 1 ruble, then the "greedy" algorithm works - in the cycle, pay with the largest bill that you have and does not exceed the remaining amount.
- if the coins are 1 rub. no:
- - if the amount to be collected is odd, but there is no piglet, you lose.
- - if the amount to be collected is odd, and there is at least one penny, we bring it in. Let's move on to the next point.
- - if the balance of the amount to be dialed is even - we combine the coins in pairs (and we will not pay one nickel, even if we want to). And we run the greedy algorithm. If the problem is solvable, then he will cope.

Answer 2

Take a program that goes through all possible combinations of numbers from an array and counts the sums.
A way to enumerate combinations - take a number in the binary number system, in which there are as many digits as you have array elements.
Run through the array and digits of a binary number. If the number is 1, add the array element to the sum. If the sum has converged - cheers, otherwise you continue the search.

Answer 3

Alternatively, start subtracting the numbers of the array from B by enumeration, starting from the end.
For example: B=10, A=[2,3,5,5,7]
10 - 7 = 3
If 3 is in A, then good.
Next ...
10 - 5 = 5 ...
I hope I explained it clearly.
UPD: number B should not be greater than the sum of the numbers in the array.
UPD1: you also need to check the difference of numbers for occurrences from the array. Chaotically probably described everything.

Answer 4

By brute force, use the algorithm for sequential generation of combinations from an array. Here, for example, is the implementation of infostart.ru/public/240261