f********a
发帖数: 165 | 1 说是一次party完以后，有的人负责酒水费用有的人负责汽油费用有的人负责。。这样
形成一个有向图的结构，A欠B多少钱，B欠C多少钱，C可能欠A、B分别多少钱，问怎么
reduce/combine到最后形成一些pairs，比如A欠B 20，C欠A20，reduce到最后只需要C
给B20块就行。这个pairs表达的transactions做到最小。
有人说用二分图最大权匹配，还是没有懂到怎么做。。。 | d*****c
发帖数: 605 | 2 我觉得可不可以这样：计算出一个人的净收入， 比如要C要付给A 20， 要给B 10，自
己能得到 10， 那么净收入就是 -20， 也就是要付出20. 然后得到一个array, sort一
下，跟做two sum一样从两天扫，付出的多的给得到的多的。
不知道对不对，还请大神来解答。 | I*******y
发帖数: 4893 | 3 你这个算法是不对的。比如一个数列是1, 2, ..., n, 另一面是2, 3, ..., n - 1, n
+ 1
你的算法会比最优解多出将近一倍
这个问题实际上是np hard的，从partition归约，n个数放左面，两个结点放右边，每
个的权分别是左面和的一半。partition问题有解的话，这个问题的解是n，否则这个问
题的解是n+1。所以此题没有多项式时间解。应该有伪多项式时间的DP解法
【在 d*****c 的大作中提到】
: 我觉得可不可以这样：计算出一个人的净收入， 比如要C要付给A 20， 要给B 10，自
: 己能得到 10， 那么净收入就是 -20， 也就是要付出20. 然后得到一个array, sort一
: 下，跟做two sum一样从两天扫，付出的多的给得到的多的。
: 不知道对不对，还请大神来解答。
|
|
