假設(shè)有一些朋友之間互相具有債務(wù)關(guān)系，如果已知他們之間的欠款和借款金額，問(wèn)至少需要多少現(xiàn)金流才能解決它們之間的債務(wù)關(guān)系（所有借款都?xì)w還）。
例如，下圖表示三個(gè)朋友P0，P1，P2之間的債務(wù)關(guān)系，
cashFlow1.png
P0需要?dú)w還P1 1000，P0需要?dú)w還P2 2000，P1需要?dú)w還P2 5000，
如果直接按初始債務(wù)關(guān)系，需要1000+2000+5000=8000現(xiàn)金。
cashFlow2.png
使用上圖中（最佳）還款方案，則只需要3000+4000=7000現(xiàn)金。
解決方案
使用貪心方法，每一步都解決一個(gè)人的借債關(guān)系。如何選擇每一步要解決的債務(wù)關(guān)系人呢？挑選出凈借出和凈借入最大的兩個(gè)人，挑他們兩個(gè)中數(shù)值小的那個(gè)，如果凈借出的值x相對(duì)較小，則將凈借入最大的人減去x；如果凈借入的值x相對(duì)較小，則將凈借出最大的人減去x。即從最大借入的人轉(zhuǎn)移x到最大借出的人。
算法的具體步驟如下：
設(shè)有n個(gè)人，P_i，其中i從0到n-1。
- 計(jì)算每個(gè)人的凈數(shù)量。P_i的凈數(shù)量等于所有借出的和減去所有借入的和。
- 找到兩個(gè)人：最大凈借出人（正最大）和最大凈借出人（負(fù)最大），分別為maxCredit和maxDebit。最大凈借入人為P_d，最大凈借出人為P_c。
- 設(shè)x為maxCredit和maxDebit中的小者，從P_d中消去x，從P_c中消去x。更新P_c和P_d凈數(shù)量。
- 若x等于maxCredit，則P_c可以去除（債務(wù)已清0)；若x等于maxDebit，則P_d可以去除。
- 對(duì)于剩下的n-1個(gè)人，重復(fù)上面2-4。
算法的時(shí)間復(fù)雜度為O(n^2)。
