2022-01-26：最优账单平衡。
一群朋友在度假期间会相互借钱。比如说，小爱同学支付了小新同学的午餐共计 10 美元。如果小明同学支付了小爱同学的出租车钱共计 5 美元。我们可以用一个三元组 (x, y, z) 表示一次交易，表示 x 借给 y 共计 z 美元。用 0, 1, 2 表示小爱同学、小新同学和小明同学（0, 1, 2 为人的标号），上述交易可以表示为 [[0, 1, 10], [2, 0, 5]]。
给定一群人之间的交易信息列表，计算能够还清所有债务的最小次数。
注意：
一次交易会以三元组 (x, y, z) 表示，并有 x ≠ y 且 z > 0。
人的标号可能不是按顺序的，例如标号可能为 0, 1, 2 也可能为 0, 2, 6。
力扣465。
答案2022-01-26：
状态压缩的动态规划。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
trans := [][]int{{0, 1, 10}, {1, 0, 1}, {1, 2, 5}, {2, 0, 5}}
ret := minTransfers2(trans)
fmt.Println(ret)
}
func minTransfers2(transactions [][]int) int {
debt := debts(transactions)
fmt.Println(debt)
N := len(debt)
sum := 0
for _, num := range debt {
sum += num
}
dp := make([]int, 1<<N)
for i := 0; i < 1<<N; i++ {
dp[i] = -1
}
return N - process2(debt, (1<<N)-1, sum, N, dp)
}
func process2(debt []int, set, sum, N int, dp []int) int {
if dp[set] != -1 {
return dp[set]
}
ans := 0
if (set & (set - 1)) != 0 {
value := 0
max := 0
for i := 0; i < N; i++ {
value = debt[i]
if (set & (1 << i)) != 0 {
max = getMax(max, process2(debt, set^(1<<i), sum-value, N, dp))
}
}
ans = twoSelectOne(sum == 0, max+1, max)
}
dp[set] = ans
return ans
}
func debts(transactions [][]int) []int {
map0 := make(map[int]int)
for _, tran := range transactions {
map0[tran[0]] += tran[2]
map0[tran[1]] -= tran[2]
}
N := 0
for _, value := range map0 {
if value != 0 {
N++
}
}
debt := make([]int, N)
index := 0
for _, value := range map0 {
if value != 0 {
debt[index] = value
index++
}
}
return debt
}
func getMax(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func twoSelectOne(c bool, a, b int) int {
if c {
return a
} else {
return b
}
}
执行结果如下：
左神java代码
![[问题2014A02] 解答二（求和法+拆分法，由张诚纯同学提供）](https://www.kunjuke.com/file/css/thumb/7.jpg/280-180.jpg)
![[每日电路图] 7、设计一个PCB的流程及细节·总结——给外行的同学或刚入行的同学一个宏观鸟瞰电路板设计的大致流程的文章](https://www.kunjuke.com/file/css/thumb/3.jpg/280-180.jpg)
