Xác minh xem danh sách (hoặc danh sách con của danh sách đó) có giá trị thập phân có thể bằng một số tiền nhất định không.

Question

Xin chào, tôi có List<decimal> chứa các giá trị giữa] 0; 1]. Tôi muốn kiểm tra xem tổng (hoặc tổng phụ) của các giá trị này có bằng 1 (hoặc gần như không).

Tôi cũng có thể sử dụng các chức năng Linq để lọc hoặc thao tác danh sách.

kết quả mong muốn:

• Một danh sách có chứa {0,7, 0,7, 0,7} nên return false;
• Danh sách chứa {0,7, 0,3, 0,7} phải trả về giá trị đúng;
• Danh sách chứa {0,777777, 0,2, 0,1} phải trả về false;
• Danh sách chứa {0.33333, 0.33333, 0.33333} phải trả về true;
• Danh sách chứa {0,4, 0,5, 0,6, 0,3} phải trả về giá trị đúng.

Rõ ràng, tôi sẽ muốn thứ gì đó có chi phí hiệu suất thấp nhất có thể.

Answer 1

CẬP NHẬT - bây giờ không repetively tổng thử

bool isClose(IEnumerable<decimal> list, decimal epislon) { 
    return isClose(Enumerable.Empty<decimal>(),list,0,list.Sum(),epislon); 
} 
// Define other methods and classes here 
bool isClose(IEnumerable<decimal> left,IEnumerable<decimal> right, decimal leftSum,decimal rightSum, decimal epsilon) { 
    if (leftSum>=1-epsilon && leftSum<=1+epsilon) return true; 
    if (leftSum>1+epsilon) return false; 
    if (leftSum+right.Sum()< 1-epsilon) return false; 
    if (!right.Any()) return false; 

    for (var i=0;i<right.Count();i++) { 
    var skip=right.Skip(i); 
    var newItem=skip.First(); 
    if (isClose(left.Concat(skip.Take(1)),skip.Skip(1),leftSum+newItem,rightSum-newItem,epsilon)) return true; 
    } 
    return false; 
} 



isClose(new[] {0.7m,0.7m,0.7m},0.001m); // returns false 
isClose(new[] {0.7m,0.3m,0.7m},0.001m); //returns true 
isClose(new[] {0.777777m,0.2m,0.1m},0.001m); //returns false 
isClose(new[] {0.33333m,0.33333m,0.33333m},0.001m); //returns true 

EDIT 5 thử nghiệm này

isClose(new[] {0.4m, 0.5m, 0.6m, 0.3m},0.001m); //returns true 

Answer 2

Đây là số tổng hợp tập hợp con số, một trường hợp đặc biệt của vấn đề ba lô. Thật khó (NP-hoàn thành). Các thuật toán nổi tiếng nhất có độ phức tạp theo hàm mũ. Tuy nhiên, có các thuật toán gần đúng với độ phức tạp đa thức. Những câu trả lời cho câu hỏi 'có một tập hợp con tổng cộng tới 1 ± ε?'

• http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf
• http://en.wikipedia.org/wiki/Subset_sum_problem
• Knuth TAOCP (có lẽ)

Answer 3

public static bool SubListAddsTo(this IEnumerable<decimal> source, 
    decimal target, decimal tolerance) 
{ 
    decimal lowtarget = target - tolerance; 
    decimal hightarget = target + tolerance; 
    HashSet<decimal> sums = new HashSet<decimal>(); 
    sums.Add(0m); 
    List<decimal> newSums = new List<decimal>(); 

    foreach(decimal item in source) 
    { 
    foreach(decimal oldSum in sums) 
    { 
     decimal sum = oldSum + item; 
     if (sum < lowtarget) 
     { 
     newSums.Add(sum);//keep trying 
     } 
     else if (sum < hightarget) 
     { 
     return true; 
     } 
     //else { do nothing, discard } 
    } 
    foreach (decimal newSum in newSums) 
    { 
     sums.Add(newSum); 
    } 
    newSums.Clear(); 
    } 
    return false; 
} 

bộ phân tích:

List<decimal> list1 = new List<decimal>(){0.7m, 0.7m, 0.7m}; 
List<decimal> list2 = new List<decimal>(){0.7m, 0.3m, 0.7m}; 
List<decimal> list3= new List<decimal>(){0.777777m, 0.2m, 0.1m}; 
List<decimal> list4 = new List<decimal>() { 0.33333m, 0.33333m, 0.33333m }; 
List<decimal> list5 = new List<decimal>() { 0.4m, 0.5m, 0.6m, 0.3m }; 

Console.WriteLine(list1.SubListAddsTo(1m, 0.001m)); //false 
Console.WriteLine(list2.SubListAddsTo(1m, 0.001m)); //true 
Console.WriteLine(list3.SubListAddsTo(1m, 0.001m)); //false 
Console.WriteLine(list4.SubListAddsTo(1m, 0.001m)); //true 
Console.WriteLine(list5.SubListAddsTo(1m, 0.001m)); //true 

Answer 4

Đây là một, niave, phương pháp brute force chứ không phải đơn giản. Nó sẽ không hiệu quả, nhưng hy vọng nó dễ hiểu hơn.

private const decimal threshold = .001M; 

public static bool CloseEnough(decimal first, decimal second, decimal threshold) 
{ 
    return Math.Abs(first - second) < threshold; 
} 

private static bool SubsetSum(List<decimal> data, int desiredSum) 
{ 

    int numIteratons = (int)Math.Pow(2, data.Count); 

    for (int i = 1; i < numIteratons; i++) 
    { 
     decimal sum = 0; 
     int mask = 1; 
     for (int j = 0; j < data.Count && sum < desiredSum + threshold; j++) 
     { 
      if ((i & mask) > 0) 
      { 
       sum += data[j]; 
      } 
      mask <<= 1; 
     } 

     if (CloseEnough(sum, desiredSum, threshold)) 
     { 
      return true; 
     } 
    } 

    return false; 
} 

Answer 5

chỉnh sửa: mã ban đầu của tôi không cho phép xấp xỉ (0,9999 = 1).

Điều này sử dụng bitmap về số lượng biến thể để che dấu các giá trị trong mảng nguồn nhằm bạo lực tất cả các biến thể.

Tốc độ này nhanh hơn khoảng 7,5 lần so với câu trả lời được chấp nhận khi được kiểm tra trên tất cả năm trường hợp thử nghiệm trong vòng lặp triệu (khoảng 41 giây so với khoảng 5,5 giây). Nó nhanh hơn gấp hai lần so với tốc độ của David B và nhanh hơn khoảng 15% so với tốc độ của Servy.

public static bool Test(decimal[] list, decimal epsilon) 
    { 
     var listLength = list.Length; 
     var variations = (int)(Math.Pow(2, listLength) - 1); 
     var bits = new bool[9]; 

     for (var variation = variations; variation > 0; variation--) 
     { 
      decimal sum = 0; 

      bits[1] = (variation & 1) == 1; 
      bits[2] = (variation & 2) == 2; 
      bits[3] = (variation & 4) == 4; 
      bits[4] = (variation & 8) == 8; 
      bits[5] = (variation & 16) == 16; 
      bits[6] = (variation & 32) == 32; 
      bits[7] = (variation & 64) == 64; 
      bits[8] = (variation & 128) == 128; 

      for (var bit = listLength; bit > 0; bit--) 
      { 
       if (bits[bit]) 
       { 
        sum += list[bit - 1]; 
       } 
      } 

      if (Math.Abs(sum - 1) < epsilon) 
      { 
       return true; 
      } 
     } 

     return false; 
    } 

chỉnh sửa: phiên bản NewTest này là nhanh hơn so với phiên bản trên 30% và là nhanh hơn so với giải pháp chấp nhận hơn mười lần. Nó loại bỏ việc xây dựng mảng để tìm ra bitmask có lợi cho cách tiếp cận của Servy, nơi mà phần lớn sự cải tiến đến từ đó. Nó cũng loại bỏ cuộc gọi Math.Abs ​​giúp cải thiện biên.

private const decimal Epislon = 0.001m; 
    private const decimal Upper = 1 + Epislon; 
    private const decimal Lower = 1 - Epislon; 

    private static bool NewTest(decimal[] list) 
    { 
     var listLength = list.Length; 
     var variations = (int)(Math.Pow(2, listLength) - 1); 

     for (var variation = variations; variation > 0; variation--) 
     { 
      decimal sum = 0; 
      int mask = 1; 

      for (var bit = listLength; bit > 0; bit--) 
      { 
       if ((variation & mask) == mask) 
       { 
        sum += list[bit - 1]; 
       } 
       mask <<= 1; 
      } 

      if (sum > Lower && sum < Upper) 
      { 
       return true; 
      } 
     } 

     return false; 
    }