Algo для оплаты устройства сумма предложения для оплаты наличными

Question

У меня были проблемы с рюкзаком и т. Д., Но я не уверен, попадает ли эта проблема в ту или иную область, и независимо от того, как ее решить.Вот вопрос:

Suppose we are given a set of denominations {1, 2, 10, 20, 50, 100}. A customer is checking out and is paying in cash. How we suggest the top 6 or top x choices on our own payment screen based on what amount the customer may have handed over. For example if customer has to pay 87$, customer might hand over 5 bills of 100, or 4 bills of 20 and a 5 and a 2, etc Я не могу придумать алгоритм, хотя у меня возникает ощущение, что это проблема рюкзака, но с несколькими ответами для данного значения?

Answer 1

Одна важная вещь, которую стоит упомянуть, это то, что вы должны получить более конкретные требования.Очень важно сидеть с клиентом, готовить примеры и задавать им вопросы: «Я должен заплатить 87, я даю вам 87x 1 доллар, хорошо это или нет и почему».Из более очевидного вы получите: «что лучше 50х2 или 50 + 20 + 20 и почему».Чтобы создать алгоритм чего угодно, сначала нужно уметь сказать, как бы вы поступили как человек (с неограниченным временем и большим терпением), а затем вы можете его реализовать.

Одна довольно простая метрика здесь заключается в том, чтоВы хотите, чтобы стоимость была как можно ближе к реальной сумме, а также вы не хотите платить слишком большими счетами, верно?

Итак, мы должны найти все решения, а затем подсчитать счет (меньше счетов и больше близко к цели).цените лучшее), сортируйте по баллам и берите «х» из лучших.

Вы можете улучшить функцию «баллов», т.е. предпочтительны счета «10 и 20», чтобы они давали вам лучший балл, используя их,Или меньшее количество счетов более важно, чем разница между целевым значением и суммой ваших счетов, поэтому вы штрафуете счета больше (например, каждая разница в 10 долларов имеет такое же наказание, что и 1 счет больше)

Это работает javascriptкод основан на возврате.

// const countables = [100, 50, 20, 10, 2, 1];
// const targetAmount = 87;

const countables = [5, 2, 1];
const targetAmount = 13;


const payments = [];
const solutions = [];
let index = 0;

let end = false;
let i = 0;

while (end === false) {
    const sum = payments.reduce((prev, val) => prev + val, 0);
    if (sum >= targetAmount) {
        solutions.push({
            sum,
            score: countTheScore(payments, targetAmount, sum),
            payments: [...payments],
        })
        index++;
        if (index === countables.length) {
            let popped = null;
            do {
                popped = payments.pop();
            } while (popped === countables[countables.length - 1]);
            if (payments.length === 0) {
                end = true;
            }
            const indexOfLastNonLowest = countables.indexOf(popped);
            index = indexOfLastNonLowest + 1;
        } else {
            payments.pop();
        }
    } else {
        payments.push(countables[index]);
    }
}


function countTheScore(payments, targetAmount, sum) {
    amount = payments.length;
    difference = sum - targetAmount;
    return amount + difference;
}

console.log(solutions.sort((a, b) => a.score - b.score));
// const sortedSolutions = solutions.sort((a, b) => a.score - b.score);
// const bestSolutions = [];
// for (var j=0; j < 5; j++) {
//     bestSolutions.push(sortedSolutions[j]);
// }
// console.log(bestSolutions);

Здесь выводятся все решения, отсортированные от лучших к худшим:

[ { sum: 13, score: 4, payments: [ 5, 5, 2, 1 ] },
  { sum: 15, score: 5, payments: [ 5, 5, 5 ] },
  { sum: 14, score: 5, payments: [ 5, 5, 2, 2 ] },
  { sum: 13, score: 5, payments: [ 5, 5, 1, 1, 1 ] },
  { sum: 13, score: 5, payments: [ 5, 2, 2, 2, 2 ] },
  { sum: 13, score: 6, payments: [ 5, 2, 2, 2, 1, 1 ] },
  { sum: 13, score: 7, payments: [ 5, 2, 2, 1, 1, 1, 1 ] },
  { sum: 13, score: 8, payments: [ 5, 2, 1, 1, 1, 1, 1, 1 ] },
  { sum: 13, score: 9, payments: [ 5, 1, 1, 1, 1, 1, 1, 1, 1 ] } ]

(чем ниже оценка, тем лучше)

Для ваших исходных требований это будет выходной результат 5:

[ { sum: 90, score: 6, payments: [ 50, 20, 20 ] },
  { sum: 90, score: 7, payments: [ 50, 20, 10, 10 ] },
  { sum: 87, score: 7, payments: [ 50, 20, 10, 2, 2, 2, 1 ] },
  { sum: 87, score: 8, payments: [ 50, 10, 10, 10, 2, 2, 2, 1 ] },
  { sum: 90, score: 8, payments: [ 50, 10, 10, 10, 10 ] } ]

---

Кстати: если я изменю функцию оценки на

function countTheScore(payments, targetAmount, sum) {
    amount = payments.length*3;
    difference = sum - targetAmount;
    return amount + difference;
}

, то результат будет, вероятно,более точно к тому, что вам нужно

[ { sum: 90, score: 12, payments: [ 50, 20, 20 ] },
  { sum: 90, score: 15, payments: [ 50, 20, 10, 10 ] },
  { sum: 100, score: 16, payments: [ 100 ] },
  { sum: 90, score: 18, payments: [ 50, 10, 10, 10, 10 ] },
  { sum: 100, score: 19, payments: [ 50, 50 ] } ]

Вы можете немного поиграть с этими показателями и выяснить, какой из них наилучший для вас.