Coin spending problem. Help improve the time complexity, please.

[prestokeys]

I'm only asking for a description (pseudocode) for a better method.

allSuitablePayments (int price, const std::array<int,N>& coinsPossessed)
is a function that is to return a list of all possible std::array<int,N>'s
that represent the amounts of each coin being spent to purchase an item whose price is 'price'. The rule, however, is that no redundant coin be spent.
For example, if 4 Zlots are enough to purchase an item, then a 5th Zlot shall not be given to the cashier (nor shall any other coin type be given on top of the 4 Zlots).

The pack 'CoinValues...' is the value of each coin, and the elements of the array 'coinsPossessed' represents how much of each coin the customer has (the coin types being in the same order as 'CoinValues...').

Here is an example. Suppose <CoinValues...> is <1,5,10,25> and coinsPossessed = {5,2,3,4}. This means you have 5 pennies, 2 nickels, 3 dimes, and 4 quarters. Suppose you want to buy an item whose price is 54 cents. Then some possible payments allowed are:
- 3 quarters
- 2 quarters, 1 nickel
- 2 quarters, 4 pennies
- 1 quarter, 3 dimes,
etc...
and this would be outputted by 'allSuitablePayments' as
{ {0,0,0,3}, {0,1,0,2}, {4,0,0,2}, {0,0,3,1}, ...}

My solution below is far too slow, because I first generate ALL possible payments, and then I remove all payments that either are short in change, or has a redundant coin.

template <std::size_t N>
std::list<std::array<int, N>> generateArraysHelper (std::list<std::array<int, N>>& all, const std::array<int, N>& limits, std::size_t index) {
	std::list<std::array<int, N>> newArrays;
	for (std::array<int, N>& a : all)
		for (int i = 0; i <= limits[index]; i++) {  // Spawn first+1 new arrays.
			std::array<int, N> newA = a;
			newA[index] = i;
			newArrays.emplace_back(newA);
		}
	if (index == N - 1)
		return newArrays;
	return generateArraysHelper<N>(newArrays, limits, index + 1);	
}

// Returns a list of all array<int, N>'s with each component ranging from 0 to the corresponding value specified in 'limits'.
// For example generateArrays<5>({2,2,2,2,2}) will yield the list of all array<int, 5>'s with each component being 0, 1, or 2.
template <std::size_t N>
std::list<std::array<int, N>> generateArrays (const std::array<int, N>& limits) {
	std::list<std::array<int, N>> all = { {0} };
	return generateArraysHelper<N> (all, limits, 0);
}

// Take ALL possible array values for coinsPaid.  Remove those that total up less than 'price' and remove those that don't meet the 
// the main condition of the problem (i.e. has a redundant coin in the sense that if a coin is removed, it is still totals up greater than 'price').
template <int... CoinValues>
std::list<std::array<int, sizeof...(CoinValues)>> allSuitablePayments (int price, const std::array<int, sizeof...(CoinValues)>& coinsPossessed) {
	constexpr std::size_t N = sizeof...(CoinValues);
	std::list<std::array<int, N>> candidates = generateArrays<N>(coinsPossessed);
	// Now we remove from 'candidates' all arrays that fail to meet the value 'price' or has a redundant coin.
	candidates.remove_if ([price](const std::array<int, N>& x)->bool {
		if (totalAmount<N, CoinValues...>(x) < price)
			return true;  // Since x fails to be enough to pay for the item with value 'price'.
		for (std::size_t i = 0; i < N; i++) {
			if (x[i] == 0)
				continue;
			std::array<int, N> a = x;
			a[i]--;  // Remove one coin of the ith type.
			if (totalAmount<N, CoinValues...>(a) >= price)
				return true;  // Removing one coin of the ith type still yields an amount >= price, so that ith coin is redundant.  This means that x has a redundant coin.
		}
		return false;
	});
	return candidates;
}

int main() {
    const std::list<std::array<int, 5>> suitablePayments = allSuitablePayments<1,10,25,50,100>(151, {30,4,5,2,1});  // 37 possibilities
}

The function totalAmount I did not post above because I don't want to clutter the ideas with other functions (but if you want it I can post that too). The reason I need to improve the time complexity is because in my main program, the coins possessed are usually in the hundreds (or more).

[ne555]

> I first generate ALL possible payments
> the coins possessed are usually in the hundreds (or more).
¿don't you bother to do a run time analysis before start coding?
The complexity is O( \prod K_j ) where K_j is the amount of coins of type `j'

You may use dynamic programming for O( n*\sum K_j ) where `n' is the price that you want.
¿is that good enough for you?


> return a list of all possible std::array<int,N>'s
that's going to be a big list.
Given that you'll have a lot of prefixes, perhaps a trie would be suitable to represent it.

[dhayden]

Do it recursively. In the example you gave (54 cent payment) start with one quarter, then solve for 29 cents (54 minus the quarter). Then take 2 quarters and solve for 4 cents (54-2*25).

Now move down to the dimes. Note that when you do the solutions with dimes, you don't need to include any quarters because you've already found those solutions.

[prestokeys]

Following the spirit of recursion:

Let a[i] be the list of all arrays representing all the allowable ways to spend the coins to make the purchase of an item of price i, without any redundant coin being given.
Then a[i+1] = the elements of a[i] that total to i+1 or more, and the elements of a[i] that total to less than i+1 "combined" (with certain checks) with a[difference], where the values of 'difference' are i+1 - those insufficient totals.
The base case a[1] is simply {{1,0,0,...}, {0,1,0,0,...}, ...}, i.e. one of each coin.

Will this algorithm work? If so, how does its time complexity compare with dhayden's method (which I didn't implement yet)?

Update:
This algorithm I described works. It gives the correct output and its time complexity is not affected by how many coins the customer has. But I don't know how to determine its time complexity. What is the time complexity of dhayden's algorithm (which I'll try coding now)?

constexpr std::size_t N = sizeof...(CoinValues);
// Let candidates[i] be the list of all arrays representing all the allowable ways to spend the coins to make the purchase of an item of price i, without any redundant coin being given.
std::vector<std::list<std::array<int, N>>> candidates(price+1);
for (int i = 0; i < N; i++) {  // Base case.
	std::array<int, N> singleCoin = {0};
	singleCoin[i] = 1;  // One coin of each type certainly can pay for an item whose price is 1.
	candidates[1].emplace_back(singleCoin);
}
for (int i = 2; i <= price; i++) {
	for (const std::array<int, N>& x : candidates[i-1]) {
		const int amount = totalAmount<N, CoinValues...>(x);
		if (amount >= i) {  // x, which is enough to pay amount i-1, is also enough to pay amount i, so it is inserted in candidates[i].
			candidates[i].emplace_back(x);
			continue;
		}
		const int amountStillNeeded = i - amount;
		for (const std::array<int, N>& y : candidates[amountStillNeeded]) {
			if (totalAmount<N, CoinValues...>(y) >= i)
				continue;  // Adding any coin to y will make it a redundant coin, so y cannot be used.
			std::array<int, N> z;  // The possible payments of amountStillNeeded can be "joined" to x, which will then be sufficient to pay amount i.
			bool allowed = true;
			for (int j = 0; j < N; j++) {
				z[j] = x[j] + y[j];  // z cannot be already an element in candidates[i] because (proof needed???).
				if (z[j] > coinsPossessed[j]) {
					allowed = false;  // z will certainly be enough to pay the amount i, but it surpasses the amount of coins the customer has.
					break;
				}
			}
                        if (!allowed) continue;
			for (int j = 0; j < N; j++) {  // Check if z has any redundant coin.  This is possible even though x and y themselves do not have any redundant coin.
				if (z[j] == 0)
					continue;
				std::array<int, N> test = z;
				test[j]--;
				if (totalAmount<N, CoinValues...>(test) >= i) {
					allowed = false;  // Removing a coin still results in 'test' being enough to purchase amount i, so 'test' has a redundant coin.
					break;					
				}
			}
			if (allowed)  // z is sufficient to pay, has no redundant coin, and the customer has enough coins to pay according to z.
				candidates[i].emplace_back(z);	
		}
	}
}
return candidates[price];

[ne555]

dhayden method:
explore all values from `price' to 0
try with 0 to K[i] coins
O(n*\sum K[i])

prestokey method:
explore all the values from 0 to `price'
check the result of the previous pass
O(n*\sum a[i].size())
(you'll need to see how a[i].size() grows)

[prestokeys]

Here is my implementation of dhayden's method, using pure recursion without any tabulation or memoization. It gives the exact same output as the one above. But I'm not sure if my implementation of it is still O(n*\sum K[i]) as asserted by ne555, and if it calculates identical subproblems redundantly. Does it? And I think CoinValues... needs to be sorted if it is not already sorted (instead of the order quarters, dimes, nickels pennies, a different order will give a wrong answer I think).

template <std::size_t N, int Last>
void solveCoinsHelper (int price, const std::array<int, N>& coinsPossessed, int n, std::array<int, N>& coinsGiven, std::list<std::array<int, N>>& list) {
	if (Last * coinsPossessed[n] < price)
		return;  // Since there is no other coin left to pay the amount price and these are not enough.
	coinsGiven[n] = (price % Last == 0) ? price / Last : price / Last + 1;  // Since there is no other coin left to pay the amount price.
	list.emplace_back (coinsGiven);
}

#include <conio.h>
template <std::size_t N, int First, int... Rest>
void solveCoinsHelper (int price, const std::array<int, N>& coinsPossessed, int n, const std::array<int, N>& coinsGiven, std::list<std::array<int, N>>& list) {
	if (price == 0) {
		list.emplace_back (coinsGiven);  // Since no other coin needs to be added to coinsGiven.
		return;
	}
	const int ratio = (price % First == 0) ? price / First : price / First + 1;
	for (int i = 0;  i <= std::min (ratio, coinsPossessed[n]);  i++) {  // Up to std::min (ratio, coinsPossessed[n]) coins of the ith type can be given to the cashier.
		std::array<int, N> newArray = coinsGiven;
		newArray[n] = i;
		solveCoinsHelper<N, Rest...> (std::max (price - i * First, 0), coinsPossessed, n+1, newArray, list);  // Use the next coin type with the new price 'price - i * First'.
	}
}

template <int... CoinValues>
void solveCoins (int price, const std::array<int, sizeof...(CoinValues)>& coinsPossessed, std::list<std::array<int, sizeof...(CoinValues)>>& list) {
	constexpr std::size_t N = sizeof...(CoinValues);
	std::array<int, N> array = {0};
	solveCoinsHelper<N, CoinValues...>(price, coinsPossessed, 0, array, list);
}

template <int... CoinValues>
std::list<std::array<int, sizeof...(CoinValues)>> allSuitablePayments (int price, const std::array<int, sizeof...(CoinValues)>& coinsPossessed) {
	std::list<std::array<int, sizeof...(CoinValues)>> candidates;
	// CoinValues... does NOT need to be reverse-sorted!
	solveCoins<CoinValues...> (price, coinsPossessed, candidates);  // candidates is populated here.
	return candidates;
}