f*****m
发帖数: 75 | 1 onsite的一个问题 他们直接上pair programming 给你一个ruby的ide 程序写好而且测
试要跑通 他们预先写好了几个测试
比如说有甲乙丙三个人， 甲借给乙100块钱 乙借给丙100块钱 等还钱等时候 程序要求
产生尽量少交易 直接让丙还甲100块
我搞了个greedy的解法 虽然把他们的测试都搞定了 但是我又找到一个特殊情况不是最
优解 高人有啥建议 我感觉这个是NP问题 跟背包挺像都 |
p*u
发帖数: 136 | 2 同样只能想到greedy的算法，无法证明正确性
先算出来每个人是应收多收钱，还是应支付多少钱。这样得到2个集合，1个是应收，1
个是应付。
每次在应付找个最大值，给应收最大值还款。重复这个过程，迭代下去。
楼主能说下你的特殊情况是啥？
【在 f*****m 的大作中提到】
: onsite的一个问题 他们直接上pair programming 给你一个ruby的ide 程序写好而且测
: 试要跑通 他们预先写好了几个测试
: 比如说有甲乙丙三个人， 甲借给乙100块钱 乙借给丙100块钱 等还钱等时候 程序要求
: 产生尽量少交易 直接让丙还甲100块
: 我搞了个greedy的解法 虽然把他们的测试都搞定了 但是我又找到一个特殊情况不是最
: 优解 高人有啥建议 我感觉这个是NP问题 跟背包挺像都
|
l*********8
发帖数: 4642 | 3 这是subset sum problem (sum to zeros). NP-complete.
【在 f*****m 的大作中提到】
: onsite的一个问题 他们直接上pair programming 给你一个ruby的ide 程序写好而且测
: 试要跑通 他们预先写好了几个测试
: 比如说有甲乙丙三个人， 甲借给乙100块钱 乙借给丙100块钱 等还钱等时候 程序要求
: 产生尽量少交易 直接让丙还甲100块
: 我搞了个greedy的解法 虽然把他们的测试都搞定了 但是我又找到一个特殊情况不是最
: 优解 高人有啥建议 我感觉这个是NP问题 跟背包挺像都
|
h*******e
发帖数: 1377 | 4 怎么感觉是dfs寻找距离大于2的路或者环，之后整条路流量减去流量deltaC，如果
是路增加流量为deltaC的距离为一的路。 repeat上面过程直到找不到距离大于2
的路或者环。 |
e********2
发帖数: 495 | 5 就是最大流算法，把任意两点见的最大流算出来就行了。
【在 h*******e 的大作中提到】
: 怎么感觉是dfs寻找距离大于2的路或者环，之后整条路流量减去流量deltaC，如果
: 是路增加流量为deltaC的距离为一的路。 repeat上面过程直到找不到距离大于2
: 的路或者环。
|
e********2
发帖数: 495 | 6 或者算出每个点的尽出入，尽出入为0的点删去，尽出入不为0的组成一根链表或一棵树
就行了，顶多再配一下对，有几棵树就更好了。
【在 f*****m 的大作中提到】
: onsite的一个问题 他们直接上pair programming 给你一个ruby的ide 程序写好而且测
: 试要跑通 他们预先写好了几个测试
: 比如说有甲乙丙三个人， 甲借给乙100块钱 乙借给丙100块钱 等还钱等时候 程序要求
: 产生尽量少交易 直接让丙还甲100块
: 我搞了个greedy的解法 虽然把他们的测试都搞定了 但是我又找到一个特殊情况不是最
: 优解 高人有啥建议 我感觉这个是NP问题 跟背包挺像都
|
e********2
发帖数: 495 | 7 然后就真的转化成最大流问题的变体，有几个源，有几个汇，然后源和汇之间的
channel capacity无限大，要求用尽可能少的channel。
【在 e********2 的大作中提到】
: 或者算出每个点的尽出入，尽出入为0的点删去，尽出入不为0的组成一根链表或一棵树
: 就行了，顶多再配一下对，有几棵树就更好了。
|
e********2
发帖数: 495 | 8 最好都要N/2次transaction，所以N次transactions也挺好的。
【在 e********2 的大作中提到】
: 然后就真的转化成最大流问题的变体，有几个源，有几个汇，然后源和汇之间的
: channel capacity无限大，要求用尽可能少的channel。
|
l*********8
发帖数: 4642 | 9 时间复杂度多少？
【在 e********2 的大作中提到】
: 然后就真的转化成最大流问题的变体，有几个源，有几个汇，然后源和汇之间的
: channel capacity无限大，要求用尽可能少的channel。
|
h*******e
发帖数: 1377 | 10 不是算任意两点最大流吧。。。
A->B->C
5 2
A 和 B 的最大流是 ５ A->Ｃ最大流是 ２ 。。。明显A 很倒霉么。。 给了７块钱
【在 e********2 的大作中提到】
: 就是最大流算法，把任意两点见的最大流算出来就行了。
|
b***e
发帖数: 1419 | 11 30 100 100
30 80 120
从最小的贪心匹配貌似可以。
1
【在 p*u 的大作中提到】
: 同样只能想到greedy的算法，无法证明正确性
: 先算出来每个人是应收多收钱，还是应支付多少钱。这样得到2个集合，1个是应收，1
: 个是应付。
: 每次在应付找个最大值，给应收最大值还款。重复这个过程，迭代下去。
: 楼主能说下你的特殊情况是啥？
|
