пусть a, b, c - номиналы монет, x, y, z - количество монет каждого номинала и e - сумма которую нужно набрать. Получается выражение x * a + y * b + z * c = e.
- это не правильное выражение (точнее оно будет верным только в частном случае, когда искомая сумма будет равна количеству всех имеющихся денег)
x[i] * a + y[j] * b + z[k] * c = e - вот это правильное
Что мы знаем из входных данных? мы знаем сколько у нас есть денег всего, это как раз x * a + y * b + z * c, пусть это будет N;
Дальше мы знаем сумму которую необходимо набрать это e;
Нам нужно понять сколько раз мы можем получить e из N, пусть это будет Q
N / e = M - количество способов получить e математически
Это нам не подходит так как нам надо учитывать номиналы, но теперь у нас есть ограничение
0 <= Q <= M
это к вопросу
как убедиться что я получу наибольшее количество
Дальше будет вариант решения задачи неоптимальным способом "как получится" (смотри статус профиля)
более правильным вариантом будет почитать другие ответы на вопрос и составить собственный вариант решения задачи с учетом теории из линейного программирования
1. понять, какие номиналы будут участвовать в получение e (и есть ли они у нас в целом)
2. отсечь случай e === N
3. получить все комбинации для получения e
4. понять какие из них сочитаются между собой с учетом ограниченности монет
5. найти наибольшее количество сочитаемых
Дальше предоставляю говнокод на js который решает эту задачу как минимум в частных случаях (я проверил парочку вариантов входных параметров)
Оно
// Входные параметры
const a = 1;
const b = 2;
const c = 5;
const x = 3;
const y = 2;
const z = 2;
const e = 7;
// Отсекаем лишнее
let params = [];
if (getEntryNominal(c, e) >= 1) {
params.push({
'count': z,
'nominal': c
});
}
if (getEntryNominal(b, e) >= 1) {
params.push({
'count': y,
'nominal': b
});
}
if (getEntryNominal(a, e) >= 1) {
params.push({
'count': x,
'nominal': a
});
}
let count = 0;
const N = getN(a, b, c, x, y, z);
if (N === e) {
count = 1;
} else {
count = getCombinationsAll(params, e)
}
console.log(count);
function getN(a, b, c, x, y, z) {
return x * a + y * b + z * c;
}
function getEntryNominal(nominal, e) {
return Math.floor(e / nominal);
}
function getCombinationsAll(params, e) {
let Q = 0;
let combinations = [];
let maxLength = parseInt() + parseInt(params[1]?.count) + parseInt((params[2])?.count ?? 0);
const iM = (params[0]?.count ?? 0);
const jM = (params[1]?.count ?? 0);
const kM = (params[2]?.count ?? 0);
let i = iM;
let j = jM;
let k = kM;
let a = (params[0]?.nominal ?? 0);
let b = (params[1]?.nominal ?? 0);
let c = (params[2]?.nominal ?? 0);
// Вычисляем количество всех возможных комбинаций из которых получается e
while (i + j + k > 0) {
let bufE = getN((params[0]?.nominal ?? 0), (params[1]?.nominal ?? 0), (params[2]?.nominal ?? 0), i, j, k);
if (bufE === e) {
let obj = {};
obj[a] = i;
obj[b] = j;
obj[c] = k;
combinations.push(obj);
}
k--;
if (k < 0) {
j--;
k = kM;
}
if (j < 0) {
i--;
j = jM;
}
if (i < 0) {
i = 0
}
}
console.log(combinations);
// составим список сочитаемых комбинаций
let combComb = [];
for (w = 0; w < combinations.length; w++) {
i = iM;
j = jM;
k = kM;
combComb[w] = [];
for (v = 0; v < combinations.length; v++) {
if (
i - combinations[v][a] >= 0
&& j - combinations[v][b] >= 0
&& k - combinations[v][c] >= 0
) {
i -= combinations[v][a];
j -= combinations[v][b];
k -= combinations[v][c];
combComb[w].push(combinations[v]);
}
}
}
// ищем максимальное количество комбинаций
for (w = 0; w < combComb.length; w++) {
if (combComb[w].length > Q) {
Q = combComb[w].length;
}
}
console.log(combComb);
return Q;
}
Простой
