数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中最小化给定朋友集之间的现金流（朋友之间互相借钱）
假设有一些朋友。他们之间互相借钱。所以在网络上会有一些现金流。我们的任务是最小化网络中的现金流。假设有三个朋友 P1、P2 和 P3。他们之间的现金流如下所示：
此现金流不是最小的；我们必须将其最小化。然后最终图将如下所示：
为了解决这个问题，我们将使用贪心算法。在这里，在每一步中，我们都会结算一个人的所有金额，并对剩下的 n-1 个人进行递归。现在问题来了，如何选择第一个人？答案是，计算每个人的净额，其中净额是通过从所有贷方中减去所有借方获得的。当评估净额时，然后找到两个最小和最大的节点。这两个节点分别是最大的债权人和债务人。具有最小值的人是第一个人。算法如下所示：
对于每个人 Pi，从 0 到 n – 1，执行以下步骤
计算每个人的净额。一个人的净额可以通过从所有借方的总和中减去所有贷方的总和来计算。
找到最大的债权人 Pc 和最大的债务人 Pd。假设要贷给最大债权人的最大金额为 max_credit，而从最大债务人那里借出的最大金额称为 max_debit。
设置 x：= max_credit 和 max_debit 中的最小值。然后从 Pd 中借出 x，并将 x 贷给 Pc
如果 x 等于 max_credit，则从集合中删除 Pc 并对接下来的 n-1 个人进行递归。
如果 x 等于 max_debit，则从人员集中删除 Pd 并对接下来的 n-1 个人进行递归
示例
#include<iostream>
#include<algorithm>
#define N 3
using namespace std;
int getMinIndex(int arr[]) {
int minInd = 0;
for (int i=1; i<N; i++)
if (arr[i] < arr[minInd])
minInd = i;
return minInd;
}
int getMaxIndex(int arr[]) {
int maxInd = 0;
for (int i=1; i<N; i++)
if (arr[i] > arr[maxInd])
maxInd = i;
return maxInd;
}
void cashFlowTask(int amount[]) {
int max_credit = getMaxIndex(amount), max_debit = getMinIndex(amount);
if (amount[max_credit] == 0 && amount[max_debit] == 0)
return;
int min_val = min(-amount[max_debit], amount[max_credit]);
amount[max_credit] -= min_val;
amount[max_debit] += min_val;
cout << "P" << max_debit << " sends " << min_val << " to " << "P" << max_credit << endl;
cashFlowTask(amount);
}
void minCashFlow(int graph[][N]) {
int amount[N] = {0};
for (int p=0; p<N; p++)
for (int i=0; i<N; i++)
amount[p] += (graph[i][p] - graph[p][i]);
cashFlowTask(amount);
}
int main() {
int graph[N][N] = {
{0, 1000, 2000},
{0, 0, 5000},
{0, 0, 0},};
minCashFlow(graph);
}输出
P1 sends 4000 to P2 P0 sends 3000 to P2
更新于： 2019 年 10 月 22 日
979 次查看
广告