“задача с деньгами” на react/redux

задача написать программу которая будет показывать введённое в input число мелочью начиная с самых оптимальных вариантов.

“деньги” которыми можно всё это реализовать: 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000

в инпут будут вводиться числа начиная с 1000 из списка выше

Пример с вариантами для которых код будет верным: допустим в инпут ввели число 1000

  1. 2*500
  2. один 500, две 200, один 100
  3. один 500, один 200, три 100
  4. один 500, пять 100

вот код с моими тщетными попытками, помогите пожалуйста решить https://stackblitz.com/edit/react-mxystd

Я правильно понял, что мы показываем все возможные варианты, отсортированные по количеству купюр? То есть в список попадут и 200 * 5 и 100 * 10?

да, смог сделать только первый вариант


что-то вроде этого
вот код первого варианта

 if(action.type==='changeFn'){
            temp.value=action.data
                let a = []
                for(let i=100; i < temp.value; i++){
                    for(let k=0;k<temp.currencies.length;k++){
                        if(temp.value%i==0 && temp.currencies[k].id==i){
                            console.log(temp.value/i,i,temp.currencies[k].img);
                            a.unshift({coin:temp.value/i, count:i,img:temp.currencies[k].img})
                        }else if(isNaN(temp.value)){
                            temp.error='fill in only numbers'
                        }else if(temp.value>100000){
                            temp.error='there are not such currency'
                            temp.value=''
                            temp.results.length=0
                        }
                    }
                    
                }

                temp.results=a

            return temp
        }

Хорошо. Какие-то дополнительные условия? Например, мы знаем, что начальный массив каким-то образом отсортирован?

нет, к сожалению доп. условий нету,и массив я не сортировал просто unshift() сделал

Простое, но, как обычно, не самое оптимальное решение - брать каждую купюру, которая меньше общей суммы, вычитать ее из суммы, и проверять, сколько осталось. Если больше ноля - повторить с той же купюрой, или со следующей. Если 0 - мы подобрали подходящий набор купюр, складываем его в стопочку. В конце сортируем по количеству купюр.
Ну и я исходил из предположения, что у нас валидный ввод, и не будет, например, купюры достоинством в 0 или -1.

Сложность, вроде бы O(n^2) Мне кажется, что где-то должно быть более оптимальное решение, например, динамическим программированием, но я не могу его сходу придумать:

const splitMoney = (amount, available) => {
	const result = [];

	const getBills = (remainingAmount, currentStack, currentIndex) => {
		if(!remainingAmount) {
			result.push(currentStack);
			return;
		}

		if(remainingAmount < 0 || currentIndex >= available.length) {
			return;
		}

		for(let i = currentIndex; i<available.length; i++) {
			if(available[i] <= remainingAmount) {
				let billCount = 1;
				while(remainingAmount >= available[i]*billCount) {
					getBills(remainingAmount - available[i]*billCount, currentStack.concat(Array(billCount).fill(available[i])), i+1)
					billCount+=1;
				}
			}
		}
	}

	for(let i = 0; i<available.length; i++) {
		if(available[i] <= amount) {
			let billCount = 1;
			while(amount >= available[i]*billCount) {
				getBills(amount - available[i]*billCount, Array(billCount).fill(available[i]), i+1)
				billCount+=1;
			}
		}
	}

	return result.sort((a, b) => a.length - b.length);
}

console.log(splitMoney(1000, [500, 200, 100]));

Как вариант, можно попробовать сначала отсортировать купюры и потом перебирать от большей к меньшей, начиная с максимального количества купюр. Тогда в конце не нужно будет сортировать и это будет потенциально быстрее.

Edit: вот похожая задача, там обсуждается несколько вариантов решения

https://stackblitz.com/edit/react-mxystd

Import error, can't find files:

**./index.css**
**./serviceWorker**
**./redux/reducers/root**
**./App.css**

В целом задача ясна, интересна и не особо сложна, если ее визуализировать ручкой на листке бумаги, я даже загуглил кучу ее вариаций, типа “Задача банкомат”, " Задача о рюкзаке"…

В вашем решении будет интересно увидеть использование рекурсивных функций. И алгоритм вынесенный в отдельный файл, а не написанный прямо в редьюсере. Вывод функции расчета getAllNominals(input) { return {}; } и ее дальнейшая визуалиция в реакте должны быть разнесены. Здесь собственно не реакт/редакс, а чистый javascript.

спасибо большое, вы мне очень помогли

1 симпатия