몇 가지 기준에 따라 기존 컬렉션에서 새 목록을 만드는 방법

Question

목록에 맞춤 개체 컬렉션이 있습니다. 각 개체의 지속 시간 속성은 몇 분 (10 분 또는 15 분 또는 45 분 등)으로 설정되어 있습니다.

3 시간 내에 그룹화해야합니다. 즉, ListA는 기간 합계가 3 시간과 같아야하는 객체 컬렉션을 갖게됩니다. 하지만 최종 목록은 3 시간으로 고정 될 필요는 없습니다 (덜 작거나 같을 수도 있습니다).

개체를 목록에서 읽고 3 시간의 총 지속 시간을 기준으로 새 목록을 만드는 데 사용해야하는 알고리즘은 무엇입니까?

여기에 어려움이있을 수 있습니다. 30 분의 개체 5 개와 45 분의 개체 2 개가 있습니다. ListA에서 내가 읽었을 때 5 분의 30 분 (6 * 50 = 150)의 객체를 추가하면 1 분 45 분의 객체를 추가 할 수 없습니다. 그것은 3 시간과 같지 않기 때문입니다. 45 분짜리 객체 2 개를 먼저 추가하고 30 분짜리 객체 3 개를 다음에 (2 * 45 + 3 * 30 = 3 시간) 객체로 추가하고 다른 2 개의 객체를 다른 목록에 추가하게합니다.

읽어 주셔서 감사합니다.

Answer 1

큰 개체를 먼저 저장하고 작게 만들려고하면 쉽습니다. 여기

내가 당신을 위해 만들어 빠른 코드, 그리고 그것을 잘 작동합니다 : 예를 들어

static void Main(string[] args) 
    { 
     // data 
     List<Int32> listElement = new List<Int32>() { 10, 20, 10, 30, 45, 10, 20, 30, 40, 50, 60, 40, 30, 50, 60, 70, 80, 90, 20, 30, 10, 50, 60, 40, 60, 80, 90, 60, 80, 70, 80, 90, 90, 50 }; 
     Int32 MaxStack = 180; 

     // result 
     List<List<Int32>> listResult = new List<List<Int32>>(); 

     // process 
     foreach (Int32 element in listElement.OrderByDescending(i => i)) 
     { 
      List<Int32> listToStore = listResult.Where(l => l.Sum() + element <= MaxStack).FirstOrDefault(); 
      if (listToStore == null) 
      { 
       listToStore = new List<Int32>(); 
       listResult.Add(listToStore); 
      } 

      listToStore.Add(element); 
     } 

     // view 
     foreach (List<Int32> list in listResult) 
     { 
      Console.Write("List " + (listResult.IndexOf(list) + 1) + "[total " + list.Sum() + "]: ");     
      foreach (Int32 element in list) 
      { 
       Console.Write(element.ToString() + " "); 
      } 

      Console.WriteLine(); 
     } 

     Console.ReadKey(); 
    } 

, 그것은 INT32 객체와, 콘솔이지만, 복잡한 객체에 대해 동일합니다.

모든 것은 더 큰 것에서 더 작은 것으로 당신의 물건의 목록을 읽고, 그것을 저장할 수있는 첫번째 가게 목록을 발견하는 것입니다.

결과는 다음과 같습니다

List 1[total 180]: 90 90 
List 2[total 180]: 90 90 
List 3[total 180]: 80 80 20 
List 4[total 180]: 80 80 20 
List 5[total 180]: 70 70 40 
List 6[total 180]: 60 60 60 
List 7[total 180]: 60 60 50 10 
List 8[total 180]: 50 50 50 30 
List 9[total 175]: 45 40 40 30 20 
List 10[total 90]: 30 30 10 10 10 

편집 :

 // switching element for better fill 
     List<List<Int32>> unfilledlist = listResult.Where(l => l.Sum() < MaxStack).ToList(); 
     // truncate original result 
     unfilledlist.ForEach(l => listResult.Remove(l)); 

     while (unfilledlist != null && unfilledlist.Count > 1) 
     { 
      List<Int32> list = unfilledlist.First(); 
      unfilledlist.Remove(list); 

      foreach (Int32 element in list) 
      { 
       Int32 needed = MaxStack - list.Sum() + element; 
       Boolean isFound = false; 

       foreach (List<Int32> smallerlist in unfilledlist) 
       { 
        List<Int32> switchingList = new List<int>(); 

        // searching how to fill what we needed 
        foreach (Int32 e in smallerlist.OrderByDescending(i => i)) 
        { 
         if (e + switchingList.Sum() <= needed) 
          switchingList.Add(e); 
        } 

        // we found a possible switch 
        if (switchingList.Sum() == needed) 
        { 
         // moving first element 
         list.Remove(element); 
         smallerlist.Add(element); 

         // moving element 
         switchingList.ForEach(e => { smallerlist.Remove(e); list.Add(e); }); 
         isFound = true; 
         break; 
        } 
       } 

       if (isFound) 
        break; 
      } 

      listResult.Add(list.OrderByDescending(i => i).ToList()); 
     } 

     // completing result with lists that are not with sum 180 
     unfilledlist.ForEach(l => listResult.Add(l.OrderByDescending(i => i).ToList())); 

: 당신이 180에서 목록만큼 원하는 경우이는 과정과 뷰 사이에 추가 할 수 있습니다 (quicky와 아가씨) 코드

는이 코드에 만족하지 해요,하지만

새로운 결과를 작동하는 것 같다 :

을

List 1[total 180]: 90 90 
List 2[total 180]: 90 90 
List 3[total 180]: 80 80 20 
List 4[total 180]: 80 80 20 
List 5[total 180]: 70 70 40 
List 6[total 180]: 60 60 60 
List 7[total 180]: 60 60 50 10 
List 8[total 180]: 50 50 50 30 
List 9[total 180]: 40 40 30 30 20 10 10 
List 10[total 85]: 45 30 10