2017-09-22 115 views
0

比方說,我們有一組對象的A1,A2,...的鴻溝對象與約束

,我們還有空數組G1,G2,...克每一個都不可能只有一些包括的對象,並且具有包含對象的特定數量,例如:

  • G1可以包括〔A1,A5,A8]必須含有2個對象
  • G2可以包括[A5,A6,A7, a9,a10]必須包含3個物體
  • ...
  • 克可包括〔A1,A6,A8,A10]必須包含4個對象

什麼是檢查是否有可能分配陣列之間的物體(它是沒有必要使用所有的最好的算法對象)與上述限制條件,並儘可能獲得該分佈?

+0

是其保證對象的那筆其中(G1 ,.. gm)必須包含= n? – marvel308

+0

@ marvel308沒有。我編輯了這個問題 – Lev

+0

如果gi不包含所需數量的ai,它會是無效的嗎? – marvel308

回答

2

它是一個流動問題我們如何

  1. 假設具有與容量的邊緣到每個艾一個源S = 1
  2. 有從艾邊緣到GJ如果GJ可以包括艾。容量將等於1

  3. 它們是從每個Gj到接收器的邊緣,其容量等於其必須具有的值。

  4. 現在,如果我們運行最大流量,每個Ai將被映射到Gj。總流量應等於從Gj到匯的權重之和。
  5. 如果總和有效,那麼只需獲取流中的映射。否則它是無效
0

Ñ是物體的總數和是陣列的總數。

x=n; 
y=m+1; 
arangement_possible=true; 
while(y>=2) 
{ 
    if(x<=0) 
    { 
     arrangement_possible = false; 
     break; 
    } 
    x=x-y; 
    y=y-1; 
} 

如果安排是可能的,那麼這樣的安排可能不是。

CHK此條件

(((m個(m + 1))/ 2)-1)< = N

+0

你的算法不能滿足數組約束(關於它們可以擁有的對象),例如g1只能包含[a1,a5,a8] – Lev

+0

好吧,所以你想chk那麼你需要循環然後通過每個數組找到它。 – subha

+0

這不是一個解決方案。檢查marvel308的答案 – Lev