Лучший способ сбалансировать счета (представлены целыми числами) почти до 0 за один проход

Question

У меня есть массив банковских счетов с минимальным ежемесячным платежным требованием, и я пытаюсь найти логику для получения оптимального графика платежей.Вот структура массива:

array(4) {
  ["account_one"]=>
  array(9) {
    ["account"]=>
    string(21) "Account One"
    ["balance"]=>
    int(2500)
    ["minimum_payment"]=>
    int(1000)
  }
  ["account_two"]=>
  array(9) {
    ["account"]=>
    string(16) "Account Two"
    ["balance"]=>
    int(1500)
    ["minimum_payment"]=>
    int(500)
  }
  ["account_three"]=>
  array(9) {
    ["account"]=>
    string(10) "Account Three"
    ["balance"]=>
    int(3000)
    ["minimum_payment"]=>
    int(750)
  }
  ["account_four"]=>
  array(9) {
    ["account"]=>
    string(14) "Account Four"
    ["balance"]=>
    int(3000)
    ["minimum_payment"]=>
    int(750)
  }
}

В этом примере общая сумма денег на счетах составляет 10000, и ее необходимо перемещать между каждой учетной записью, чтобы выполнить требование минимального платежа.График платежей также должен быть максимально эффективным, с наименьшим количеством платежей для удовлетворения требований.Это простой пример, но в работе у нас может быть 15 или более учетных записей с различными минимальными суммами платежей.

То, что у меня есть, не так уж и много, потому что я изо всех сил пытаюсь понять общую логикуМне нужно:

$accounts_by_amount (array of accounts sorted by balance high to low)
$accounts_reversed ($accounts_by_amount in reverse order)
$schedule = array()
foreach $accounts_by_amount as $account_a
    foreach $accounts_reversed as $account_b
        if $account_a['minimum_payment'] > $account_b['mininum_payment']
            // use higher minimum payment to reduce total payments needed
            $schedule_b[] = array(
              'from' => $account_a['account'],
              'to' => $account_b['account'],
              'amount' => $account_a['minimum_payment'],
            );
        else
            continue;

    if $schedule_b
        $schedule += $schedule_b
    else
        continue

Это не работает, очевидно, но я думаю, что я мог бы сделать это слишком сложным с циклом внутри цикла.Я не ищу кого-то, кто действительно написал бы код для меня, больше чтобы сказать мне, как глупо я нахожусь с логикой и грубым представлением о том, как составить этот график вместе с минимальным количеством платежей.

Answer 1

За исключением логики планирования, я написал что-то вроде этого, чтобы перевести и сбалансировать суммы между счетами.Надеюсь это поможет.Это в JavaScript / я оставляю на ваше усмотрение попробовать это с PHP.

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

Он будет выполняться в точке O (n) при худшем вычислении, в самом худшем случае у вас не будет достаточно денег на вашем лучшем счете, что заставит его пропустить цикл while.Но это означает, что у вас будут настоящие проблемы, а не большие обозначения O.

let accounts = [
    { id: 2, balance: 6000, minpay: 4000 },
    { id: 1, balance: 5000, minpay: 2000 },
    { id: 3, balance: 4000, minpay: 4000 },
    { id: 4, balance: 4000, minpay: 5000 },
    { id: 6, balance: 3000, minpay: 6000 },
    { id: 5, balance: 3000, minpay: 5000 }
];

// create a map of workable balances.
let workableBalance = accounts.map(v => {
    return {
        id: v.id,
        value: v.balance - v.minpay
    }
}).sort((a,b) => {return b.value-a.value}); // sort descending;

let cursorFromBeginning = 0;
let cursorFromEnd = workableBalance.length - 1;

if (workableBalance[cursorFromEnd].value > 0) {
    console.log('All accounts have sufficient money in them.');
    return; // terminate.
}

if (workableBalance[cursorFromBeginning].value < 0) {
    console.log(`No way that we'll balance the accounts. The best account is in negatives.`);
    return; // terminate.
}

console.log('Present state of things: ', workableBalance);

while(cursorFromBeginning < cursorFromEnd) {
    // Get the balance from least available account.
    // Validate that the worst account actually needs money.
    let worstAccount = workableBalance[cursorFromEnd];
    if (worstAccount.value >= 0) {
        console.log(`All good! We're balanced`, workableBalance);
        return;
    }

    let bestAccount = workableBalance[cursorFromBeginning];
    if (bestAccount.value == 0) {
        cursorFromBeginning++;
        continue;
    }

    // Can this account single-handedly balance the next worst account?
    if (bestAccount.value >= Math.abs(worstAccount.value)) {
        // Balance the account.
        console.log(`Moving $${bestAccount.value} from account ${bestAccount.id} to ${worstAccount.id} - balancing the whole account.`);
        bestAccount.value += worstAccount.value;
        worstAccount.value = 0;
        cursorFromEnd--;
    }
    else {
        // Balance as much as we can.
        console.log(`Moving $${bestAccount.value} from account ${bestAccount.id} to ${worstAccount.id} - balancing the account partially.`);
        bestAccount.value = 0;
        worstAccount.value += bestAccount.value;
        cursorFromBeginning++;
    }
}


console.log('Things after some magic: ', workableBalance);