在對數字的最大獨特性有輕微的約束

這兒有你的算法的挑戰，在對數字的最大獨特性有輕微的約束

我有[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)

其結果將是：。我們將採取：(3, 1),(6, 1),(7, 1),(1, 2),(4, 2),(2, 3)和(5, 4)。

無論出於何種原因，我似乎無法找到任何其他方式比暴力破解它...

任何幫助是極大的讚賞:)

來源

2014-12-04 ZogStriP

你可以表達這個問題是一個最大流問題：

使容量1的邊緣從源節點到每個左邊的數字。

將容量3的邊沿從每個正確的數字設置爲匯聚節點。

對於形式（a，b）的每一對，將容量1的邊從左數a到右數b。

計算此網絡中從源到匯的最大流量。

來源

2014-12-04 11:28:52

如果有人對實現感興趣，下面是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-05 15:24:46 ZogStriP

在對數字的最大獨特性有輕微的約束

回答

相關問題