请教一个算法问题

每个人最多给两到三个人打款 想了好久 没想到 感觉有点难

听着像是在做灰产。。。

如果 正负总和是0 的话，我能想到的就是正负的分组，然后正数组随机拿出一个数，然后就是去负数组循环匹配

此时有人正在吊起来挨打

1. 正负分组
2. 负数组转为绝对值，正负分别按金额倒叙排列
3. 从负数分组中取一个数，到整数组中匹配，逻辑是：优先匹配绝对值等于负数绝对值的数据，如果没有再匹配绝对值大于负数绝对值的，最后考虑绝对值小于负数绝对值的（这里是为了尽可能避免一人给多人打款）
4. 如果打款方和收款方金额相等，那么直接将两条数据从两个数组中删除，并写入 from to 的交易数组中，如果正数的金额减去负数的绝对值，还有余额，那么将该值写回正值数组中(例如付款方A 是 -100，收款方 B 是 200，这一轮匹配后，B 依然存在原来的数组里，只是总金额变成了 100)，然后继续执行下一轮匹配逻辑！

帮你问了gpt

要解决这个问题，你可以使用PHP编写一个函数来计算用户之间的交易，以便将差价支付给合适的人。以下是一个可能的解决方案：

function calculateTransactions($users) {
    $transactions = [];

    // 将用户分为需要收款和需要支付的两组
    $receivers = array_filter($users, function($user) {
        return $user['diff'] > 0;
    });

    $payers = array_filter($users, function($user) {
        return $user['diff'] < 0;
    });

    // 对支付者和收款者分别按照差价绝对值降序排序
    usort($receivers, function($a, $b) {
        return abs($b['diff']) - abs($a['diff']);
    });

    usort($payers, function($a, $b) {
        return abs($a['diff']) - abs($b['diff']);
    });

    // 遍历支付者，为每个支付者找到合适的收款者
    foreach ($payers as $payer) {
        $remainingDiff = abs($payer['diff']);
        $index = 0;

        while ($remainingDiff > 0 && $index < count($receivers)) {
            $receiver = $receivers[$index];
            $amount = min($remainingDiff, $receiver['diff']);

            if ($amount > 0) {
                // 添加交易记录
                $transactions[] = [
                    'from' => $payer['user'],
                    'to' => $receiver['user'],
                    'amount' => $amount,
                ];

                // 更新支付者和收款者的差价
                $payer['diff'] += $amount;
                $receiver['diff'] -= $amount;

                // 如果支付者的差价已经清零，从支付者列表中移除
                if ($payer['diff'] == 0) {
                    array_splice($payers, $index, 1);
                }

                // 如果收款者的差价已经清零，从收款者列表中移除
                if ($receiver['diff'] == 0) {
                    array_splice($receivers, $index, 1);
                }

                // 更新剩余差价和索引
                $remainingDiff -= $amount;
            }

            $index++;
        }
    }

    return $transactions;
}

$users = [
    ['user' => 'A', 'diff' => 3000],
    ['user' => 'B', 'diff' => -1000],
    ['user' => 'C', 'diff' => -2000],
    ['user' => 'D', 'diff' => 500],
    ['user' => 'E', 'diff' => -1500],
    ['user' => 'F', 'diff' => 1000],
];

$transactions = calculateTransactions($users);

print_r($transactions);

这个函数会计算出每个支付者应该向哪些收款者支付多少钱，然后返回一个包含交易信息的数组。根据你提供的数据，它将返回如下的交易记录：

Array
(
    [0] => Array
        (
            [from] => B
            [to] => A
            [amount] => 1000
        )

    [1] => Array
        (
            [from] => C
            [to] => A
            [amount] => 2000
        )

    [2] => Array
        (
            [from] => E
            [to] => D
            [amount] => 500
        )

    [3] => Array
        (
            [from] => E
            [to] => F
            [amount] => 1000
        )

)

这些交易记录表示用户B向用户A支付了1000元，用户C向用户A支付了2000元，用户E向用户D支付了500元，用户E向用户F支付了1000元，以完成差价的支付。

这是一个怎么样的场景。AB是需要收款的为1000，CDEF都是需要付款的500。不管CDEF付款给谁都行？是这个意思吧

先将 users 分成收款方和付款方，然后依次将付款方的应付金额摊分到收款方列表中，由于付款次数有限制，需要事先对收款方列表按照可收款额度倒序排列，每次都尽量让收款方分摊尽可能多的欠款，代码简单写了下，不知道有没有bug

$users = [
    ['user' => 'A', 'diff' => 3000],
    ['user' => 'B', 'diff' => -1000],
    ['user' => 'C', 'diff' => -2000],
    ['user' => 'D', 'diff' => 500],
    ['user' => 'E', 'diff' => -1500],
    ['user' => 'F', 'diff' => 1000],
];

$froms = $tos = $exchanges = [];

foreach ($users as $user) {
    $name = $user['user'];
    $diff = $user['diff'];
    if ($diff < 0) {
        $froms[$name] = $diff; 
    } elseif ($diff > 0) {
        $tos[$name] = $diff;
    }
}

arsort($tos);

$max = 2;

foreach ($froms as $fromUser => $fromDiff) {
    $amount = abs($fromDiff);

    foreach ($tos as $toUser => $toDiff) {
        if (isset($exchanges[$fromUser]) && count($exchanges[$fromUser]) >= $max) {
            break;
        }

        $duty = $amount >= $toDiff ? $toDiff : $amount;
        $amount = $toDiff - $duty;
        $tos[$toUser] = $tos[$toUser] - $duty;
        $froms[$fromUser] = $froms[$fromUser] + $duty;

        if ($duty > 0) {
            $exchanges[$fromUser][$toUser] = $exchanges[$fromUser][$toUser] ?? 0;
            $exchanges[$fromUser][$toUser] += $duty;
        }

        if ($amount == 0) {
            break;
        }
    }
}

echo '========= USERS ==========' . PHP_EOL;
var_export($users);
echo PHP_EOL;
echo '========= EXCHANGES ==========' . PHP_EOL;
foreach ($exchanges as $fUser => $toU) {
    foreach ($toU as $k => $v) {
        echo "{$fUser} => {$k} : {$v}" . PHP_EOL;
    }
}

安排

namespace Tests\Feature;
use Faker\Factory;
use Illuminate\Support\Collection;

class ExampleTest extends TestCase
{

    public function test_a()
    {
        $faker = Factory::create();
        /**
         * todo 默认填充10个用户的随机转入转出数据，一个用户可能有多笔转入也可能多笔转出，因此需要按用户分组再统计
         * @var $original Collection
         */
        $original = Collection::times(10, function () use ($faker) {
            return [
                'user' => $faker->name,
                'diff' => $faker->biasedNumberBetween(-10000, 10000),
            ];
        })->mapToGroups(fn($items) => [$items['user'] => $items['diff']])
            ->map(fn($items,$key) => [
                'user' => $key,
                'diff' => $items->sum(),
                'max_match_num' => 3,
            ]);

        $original_output = $original->where('diff', '<', 0)
            ->sortBy('diff');
        [
            $this->inputFinishs, //转入完成记录
            $this->notInputFinishs,//未完成转入记录
            $this->outFinishs,//转出记录
            $this->transfers,//所有转入记录
        ] = [
            collect(),collect(),collect(),collect(),
        ];
        $output = clone $original_output;
        $input = $original->where('diff', '>', 0)
            ->sortByDesc('diff')
            ->each(function ($item,$user)use($output){
                $this->match($item, $output);
            });
        //转入完成
        $this->inputFinishs->dump();
        //转入未完成
        $this->notInputFinishs->dump();
        //转出（入）记录
        $this->transfers->dump();
        //转出未完成（转出额度未用尽）
        $output->dump();

    }

    public function match(array $input,Collection $out)
    {
        $value = $out->shift();
        if (!$value) {
            $this->notInputFinishs->put($input['user'], $input);
            return $input;
        }
        if ($value['max_match_num'] <= 0) {
            $this->notInputFinishs->put($input['user'], $input);
            return $input;
        }
        $value['max_match_num'] -= 1;

        $diff = abs($value['diff'] ?? 0);
        if ($input['diff'] < $diff) {
            $arr = [
                'form' => $value['user'],
                'to' => $input['user'],
                'amount' => $input['diff'],
            ];
            $value['diff'] = $diff - $input['diff'];
            $out->put($value['user'],$value);
            $this->transfers->push($arr);
            $this->inputFinishs->put($input['user'], $input);
            $out->sortBy('diff');
            return $input;
        }
        if ($input['diff'] === $value['diff']) {
            $arr = [
                'form' => $value['user'],
                'to' => $input['user'],
                'amount' => $diff,
            ];
            $this->transfers->push($arr);
            $this->inputFinishs->put($input['user'], $input);
            return $input;
        }

        if ($input['diff'] > $value['diff']) {
            $arr = [
                'form' => $value['user'],
                'to' => $input['user'],
                'amount' => $diff,
            ];
            $input['diff'] -= $diff;
            $this->transfers->push($arr);
            $this->match($input, $out);
        }
        return $input;
    }
}