貪婪的最大流量

Question

該用餐問題：
幾個家庭一起出去吃晚飯。爲了增加他們的社交互動，他們想坐在餐桌旁，以便同一個家庭中沒有兩個成員在同一個桌子上。假設晚餐隊伍有p家庭，並且i家庭擁有a(i)成員。此外，假設有q表格可用，並且j表格的座位容量爲b(j)。

問題是： 我們可以坐在桌子上的人數最多是多少？

編輯： 這個問題可以解決，創建一個圖形和運行最大流量算法。但如果我們有2 * 10^3頂點的Dinic算法，則全局複雜度爲O（10^6 * 10^6）= O（10^12）。

如果我們只是以一種貪婪的方式總是先坐在較大的羣體上。複雜度是O（10^6）。

所以我的問題是：

1）是否在這個問題上的工作貪婪的方法呢？

2）什麼是解決這個問題的最佳算法？

Answer 1

這是很容易拿出例子，其中這樣的座位是根本不可能的，所以這裏是一個僞代碼解決假設這個問題是可以解決的問題：

Sort each family i by a(i) in decreasing order 
Add each table j to a max-heap with b(j) as the key 

For each family i from the sorted list: 
    Pop a(i) tables from max-heap 
    Add one member of i to each table 
    Add each table j back into the max-heap with b(j) = b(j) - 1 

讓n = a(1) + a(2) + ... + a(p)（即用於最大堆的總人數）

假設二元堆，時間複雜度分別爲：

• 排序家庭：O(plog(p))
• 初始化表的最大堆：O(qlog(q))
• 所有流行和推送到/從最大堆：O(nlog(q))

給總時間複雜度O(plog(p) + qlog(q) + nlog(q))，其中O(nlog(q))將可能占主導地位。

因爲我們正在處理的整數，如果我們使用一維斗系統，最大堆，使得c是最大b(j)，然後我們將結束與剛剛O(n + c)（假設最大堆操作占主導地位），這也許更快。

最後，請提高大衛的答案，因爲證明是必需的，真棒。

Answer 2

是的，首先貪婪地坐在最大的家庭是一個正確的解決方案。我們只需要證明，在我們坐下一個最大的家庭之後，就可以正確地安置其餘的家庭。

假設一個實例是可解的。我們通過歸納證明，在貪婪算法佔據最大家族之後存在一個解決方案。基礎k = 0是顯而易見的，因爲要證明的假設是存在解決方案。歸納地說，假設存在一個擴展第一個k - 1系列貪婪的部分分配的解決方案。現在，貪婪通過坐上k這個家庭來擴展其部分任務。我們編輯已知的解決方案來恢復歸納假設。

儘管我們仍然可以找到一張表T1，其中貪婪已經坐了k家庭成員，但已知的解決方案沒有。如果在T1的已知解決方案中存在空間，請將一個k的家庭成員從貪婪沒有的表中移出。否則，已知解決方案的家庭成員不在k大家庭中，坐落在T1。由於該家庭小於第k次大，所以第012大家庭成員佔據表T2，小家庭沒有。交換這些成員。