Só um detalhe, teste o seu código com:
const availableNotes = {
20: 4,
50: 3,
100: 5
};
const value = 60;
O seu código vai retornar notes: [50]
. Ou seja, apenas uma nota de 50. Mas isso não é suficiente para dar o valor (60), pois o correto seria retornar 3 notas de 20.
E se testar com:
const availableNotes = {
20: 2
};
const value = 60;
Vai retornar:
{
notes: [ 20, 20, 20 ],
availableNotes: { '20': -1 },
availableNotesSum: -20
}
Isso porque faltou verificar se a quantidade não zerou.
Para arrumar isso, temos que modificar um pouco o código. Primeiro temos que testar com todas as notas, e se não der, testamos sem uma das notas (por exemplo, sem as notas de 100). Se não der, testamos sem as notas de 50 e assim por diante, até encontrar uma combinação que dê certo. Se todas as combinações falharem, é porque não é possível.
Ficaria assim:
// gera todas as combinações do array
function *subsets(array, offset = 0, minSize = 0) {
while (offset < array.length) {
let first = array[offset++];
for (let subset of subsets(array, offset)) {
subset.splice(0, 0, first);
if (subset.length >= minSize)
yield subset;
}
}
if (minSize === 0)
yield[];
}
function cashWithdrawal(value, availableNotes) {
let notes = [];
let availableNotesOriginal = structuredClone(availableNotes);
// array com os valores de todas as notas disponíveis
const allNotesValues = Object.keys(availableNotes).map((note) => Number(note)).sort((a, b) => b - a);
for (const subsetNotes of subsets(allNotesValues, 0, 2)) {
let remainingValue = value;
for (const noteValue of subsetNotes) {
while (remainingValue >= noteValue && availableNotes[noteValue] > 0) {
notes.push(noteValue);
remainingValue -= noteValue;
availableNotes[noteValue]--;
}
}
if (remainingValue == 0) { // se o valor zerou, é porque deu certo
const availableNotesSum = Object.entries(availableNotes).reduce((sum, [note, quantity]) => sum + Number(note) * quantity, 0);
return {
notes,
availableNotes,
availableNotesSum
};
} else {
// se não deu certo, zera o array de notas e volta para as notas disponíveis original
notes = [];
availableNotes = JSON.parse(JSON.stringify(availableNotesOriginal));
}
// se o valor não zerou, é porque não foi possível, então tenta com a próxima combinação de notas
}
return null; // se tentou todas as combinações e chegou aqui, é porque não é possível
}
let availableNotes = {
20: 4,
50: 3,
100: 5
};
let value = 60;
console.log(cashWithdrawal(value, availableNotes));
Resultado (3 notas de 20):
{
notes: [ 20, 20, 20 ],
availableNotes: { '20': 1, '50': 3, '100': 5 },
availableNotesSum: 670
}
Se eu mudar o valor para 75
, a função retorna null
, pois não é possível obter o valor desejado com as notas disponíveis. E se testar com availableNotes = { 20: 2 };
e value = 60;
, também vai retornar null
, pois também não é possível atingir o valor.
A função subsets
é uma generator function, que em vez de retornar todas as combinações de uma vez, ela "retorna" apenas uma de cada vez (isso economiza memória, pois dependendo da quantidade de notas, a quantidade de combinações possíveis pode ficar muito grande).
Como eu faço um loop pelos subsets e verifico um por um (e retorno se encontrar um que deu certo), isso faz com que o código consuma menos memória, pois eu trabalho apenas com uma combinação por vez, e em seguida a descarto para ir para a próxima.
Eu também clono o availableNotes
com structuredClone
porque se uma combinação não der certo, preciso restaurar os valores originais. Mas vc também pode trocar por JSON.parse(JSON.stringify(availableNotes))
.