0

这是给你的算法挑战，

我有一个[0..100]数字对列表，我需要找到唯一“左数”的最大数量，同时确保“右数”不超过 3个。

这是一个例子

  • (1, 1)
  • (2, 1)
  • (3, 1)
  • (4, 1)
  • (5, 1)
  • (6, 1)
  • (7, 1)
  • (1, 2)
  • (4, 2)
  • (1, 3)
  • (2, 3)
  • (5, 4)

结果将是：7。我们将采用：(3, 1), (6, 1), (7, 1), (1, 2), (4, 2),(2, 3)和(5, 4)。

无论出于何种原因，我似乎找不到任何其他方法，而不是蛮力强迫它......

任何帮助是极大的赞赏 ：）

4

2 回答 2

2

您可以将此问题表示为最大流量问题：

从源节点到每个左侧数字的容量为 1。

将每个正确数字的容量为 3 的边设置为接收器节点。

为每对形式 (a, b) 制作容量为 1 的边，从左侧编号 a 到右侧编号 b。

计算此网络中从源到汇的最大流量。

于 2014-12-04T11:28:52.760 回答
0

如果有人对实现感兴趣，这里有一个push–relabel maximum flow algorithm带有relabel-to-front选择规则的红宝石版本。

def relabel_to_front(capacities, source, sink)
  n      = capacities.length
  flow   = Array.new(n) { Array.new(n, 0) }
  height = Array.new(n, 0)
  excess = Array.new(n, 0)
  seen   = Array.new(n, 0)
  queue  = (0...n).select { |i| i != source && i != sink }.to_a

  height[source] = n - 1
  excess[source] = Float::INFINITY
  (0...n).each { |v| push(source, v, capacities, flow, excess) }

  p = 0
  while p < queue.length
    u = queue[p]
    h = height[u]
    discharge(u, capacities, flow, excess, seen, height, n)
    if height[u] > h
      queue.unshift(queue.delete_at(p))
      p = 0
    else
      p += 1
    end
  end

  flow[source].reduce(:+)
end

def push(u, v, capacities, flow, excess)
  residual_capacity = capacities[u][v] - flow[u][v]
  send = [excess[u], residual_capacity].min
  flow[u][v] += send
  flow[v][u] -= send
  excess[u] -= send
  excess[v] += send
end

def discharge(u, capacities, flow, excess, seen, height, n)
  while excess[u] > 0
    if seen[u] < n
      v = seen[u]
      if capacities[u][v] - flow[u][v] > 0 && height[u] > height[v]
        push(u, v, capacities, flow, excess)
      else
        seen[u] += 1
      end
    else
      relabel(u, capacities, flow, height, n)
      seen[u] = 0
    end
  end
end

def relabel(u, capacities, flow, height, n)
  min_height = Float::INFINITY
  (0...n).each do |v|
    if capacities[u][v] - flow[u][v] > 0
      min_height = [min_height, height[v]].min
      height[u] = min_height + 1
    end
  end
end

这是将数字对转换为数组的容量数组的代码

user_ids = Set.new
post_ids = Set.new

pairs.each do |p|
  user_ids << p[:user_id]
  post_ids << p[:post_id]
end

index_of_user_id = {}
index_of_post_id = {}

user_ids.each_with_index { |user_id, index| index_of_user_id[user_id] = 1 + index }
post_ids.each_with_index { |post_id, index| index_of_post_id[post_id] = 1 + index + user_ids.count }

source = 0
sink = user_ids.count + post_ids.count + 1
n = sink + 1

capacities = Array.new(n) { Array.new(n, 0) }
# source -> user_ids = 1
index_of_user_id.values.each { |i| capacities[source][i] = 1 }
# user_ids -> post_ids = 1
pairs.each { |p| capacities[index_of_user_id[p[:user_id]]][index_of_post_id[p[:post_id]]] = 1 }
# post_ids -> sink = 3
index_of_post_id.values.each { |i| capacities[i][sink] = 3 }
于 2014-12-05T15:24:46.827 回答