我的算法的缺陷在哪裏找到每個對的和不分K的最大子集？

Question

我已經評論了我的邏輯是什麼。它應該工作的方式是，例如，如果我們有K=3和S={1,7,2,4}，那麼每個對的總和不分的最大子集K是{1,7,4}。

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 

class Solution 
{ 
    static void Main(String[] args) 
    { 
     int k = Int32.Parse(Console.ReadLine().Split(' ')[1]); 
     var S = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse); 

     // first get all pairs in S whose sum doesn't divide k, 
     // each pair in their own subset set of S 
     var subsets = from i in S 
         from j in S 
         where i < j && ((i + j) % k != 0) 
         select new HashSet<int>() { i, j }; 

     // for each subset, for each number in the original set 
     // not already in the subset, if the number summed with 
     // every numer in the subset doesn't divide k, add the 
     // number to the subset 
     foreach(var ss in subsets) 
      foreach(int n in S.Where(q => !ss.Contains(q))) 
       if(ss.All(m => (m + n) % k != 0)) 
        ss.Add(n); 

     // get the size of the largest subset, print to console 
     int max = subsets.Select(ss => ss.Count).Max(); 
     Console.WriteLine(max); 
    } 
} 

Answer 1

你的算法的問題，也許錯的，意外的行爲是由於你的代碼中的錯誤。 （但即使你修復了這個問題，我認爲網上法官的速度太慢了，你也可能會錯過一些棘手的案例，你可以嘗試提交）。

HashSet對象subsets不會更新，因爲當您撥打Add時，該整數將被添加到另一個HashSet的副本中。

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 


public class Test 
{ 
    public static void Main(String[] args) 
    { 
     ... 
     foreach(var ss in cnt){ 
      foreach(int n in S.Where(q => !ss.Contains(q))) 
       if(ss.All(m => (m + n) % k != 0)){ 
        ss.Add(n); 
       } 
      // Log here, you will see the size is updated to 3 
      Console.WriteLine(ss.Count); 
     } 
     // Log here, it is still printing 2 !   
     foreach(var ss in cnt) 
      Console.WriteLine(ss.Count); 
     // get the size of the largest subset, print to console 
     int max = ... 
     Console.WriteLine(max); 
    } 
} 

一個簡單的解決方法是HashSet的新的全球榜第一，並且更新，列出

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 


public class Test 
{ 
    public static void Main(String[] args) 
    { 
     int k = Int32.Parse(Console.ReadLine().Split(' ')[1]); 
     var S = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse); 
     List<HashSet<int>> cnt = new List<HashSet<int>>(); 
     // first get all pairs in S whose sum doesn't divide k, 
     // each pair in their own subset set of S 
     cnt = (from i in S 
         from j in S 
         where i < j && ((i + j) % k != 0) 
         select new HashSet<int>() { i, j }).ToList(); 

     // for each subset, for each number in the original set 
     // not already in the subset, if the number summed with 
     // every numer in the subset doesn't divide k, add the 
     // number to the subset 

     foreach(var ss in cnt){ 
      foreach(int n in S.Where(q => !ss.Contains(q))) 
       if(ss.All(m => (m + n) % k != 0)){ 
        ss.Add(n); 
       } 
     } 

     // get the size of the largest subset, print to console 
     int max = cnt.Max(ss => ss.Count); 
     Console.WriteLine(max); 
    } 
} 

---

不過，這個問題可以很容易地在O(k)解決（如果不是數I/O時間是O(N)）

這裏是用C我接受代碼++

#include<bits/stdc++.h> 
using namespace std; 
int n,k,a,c[105] = {0},ans=0; 
int main() { 
    cin >> n >> k; 
    for(int i=0; i<n;i++) cin >> a, c[a%k]++; 

    for(int i=1; i<=k/2; i++){ 
     if(k%2 == 0 && i==k/2 && c[i]) ans++; 
     else ans += max(c[i], c[k-i]); 
    } 
    if(c[0] && ans) ans++; 
    if(!ans) ans++; 
    cout << ans << endl; 
    return 0; 
} 

這背後的概念是模塊化的算術：

(a+b)%k = 0 is equavalent to (a%k + b%k)%k = 0

所以實際上，我們只算多少元素模塊化k等於0,1,2 ... K-1，店面他們c[0], c[1]...c[k-1]

然後在邏輯上，對於那些號碼c[1] & c[k-1]不能同時選擇，所以我們選擇了一個較大的數目。同樣，c[2] & c[k-2]不能一起選擇等。

雖然有一些特殊情況，您可能會看到我的代碼並檢查出來。

要知道這個問題的一個更棘手的地方是（我認爲它是不好的書面問題陳述），如果結果集大小是1，那麼它總是一個有效的集合，即使唯一的元素可以被k整除。 （即，ans將永遠不會爲0）

Answer 2

在你的第二個循環，當你寫ss.Add(n); 添加「N」到HashSet的SS的副本。

so以後的foreach部分，subsets保持前面的集合。

您可以手動計算的foreach裏面最大的一個快速的解決方案

Answer 3

用你的方法，你將找出所有符合條件的數字的子集，但是你不會將數字子集添加到整體subsets。所以當你正在尋找最大的子集時，你找不到正確的子集。

foreach(var ss in subsets) 
    { 
     foreach(int n in S.Where(q => !ss.Contains(q))) 
     { 
      if(ss.All(m => (m + n) % k != 0)) 
       ss.Add(n); 
     } 
    //Add the subset ss to subsets or replace it 
    }