thuật toán để chọn một tập hợp các con số để đạt mức tối thiểu tổng

Question

Với Một tập hợp các số n[1], n[2], n[3], .... n[x] Và một số M

Tôi muốn tìm ra sự kết hợp tốt nhất của

n[a] + n[b] + n[c] + ... + n[?] >= M 

Sự kết hợp nên đạt đến mức tối thiểu cần thiết để tiếp cận hoặc vượt ra ngoài M mà không có kết hợp nào khác cho kết quả tốt hơn.

Sẽ làm điều này trong PHP để sử dụng thư viện PHP là ok. Nếu không, chỉ cần một thuật toán chung sẽ làm. Cảm ơn!

Answer 1

pseudocode: 

list<set> results; 
int m; 
list<int> a; 

// ...  

a.sort(); 

for each i in [0..a.size] 
    f(i, empty_set);  

// ... 

void f(int ind, set current_set) 
{ 
    current_set.add(a[ind]); 

    if (current_set.sum > m) 
    { 
     results.add(current_set); 
    } 
    else 
    { 
     for (int i=ind + 1; i<a.size; ++i) 
     { 
      f(i, current_set); // pass set by value 

      // if previous call reached solution, no need to continue 
      if (a[ind] + current_set.sum) > m 
       break; 
     } 
    } 
} 

// choose whatever "best" result you need from results, the one 
// with the lowest sum or lowest number of elements 

Answer 2

Tôi nghĩ rằng cách tiếp cận greedy algorithm sẽ hoạt động. Bạn mong đợi bao nhiêu số trong bộ này? Nếu nó là hợp lý thấp, bạn có thể thử backtrack, nhưng tôi sẽ không khuyên bạn nên nó cho bộ lớn.

Answer 3

Tôi nghĩ rằng đây là NP-hoàn thành (không thể tìm cách nhanh chóng để làm điều đó nói chung). Cách bạn đã đặt ra câu hỏi làm cho tôi nghĩ đến việc giải quyết liên tiếp Subset sum problems với số nguyên mục tiêu tăng đều từ M.

Trong ví dụ của bạn, không có phương pháp xác định có thể đạt được M hay không. Chỉ có một giải pháp brute-force sẽ cho bạn biết rằng nó không thể, và chỉ sau đó bạn có thể kiểm tra M + 1.

Tuy nhiên, bạn có thể muốn xem DP solution, vì điều này ít nhất sẽ cung cấp cho bạn ý tưởng về cách giải quyết vấn đề (mặc dù chậm). Ngoài ra còn có một giải pháp approximate sẽ là chính xác nếu số của bạn nhỏ. Sử dụng tính năng này. Cuối cùng, điều đáng chú ý là kích thước của bài toán được đo bằng số bit, không phải kích thước (hoặc tổng) của tập hợp.

Như đã đề cập ở trên, điều này có liên quan đến Knapsack problem.

Answer 4

Loại sự cố này được gọi là số nhị phân linear programming (trường hợp đặc biệt của lập trình tuyến tính số nguyên). Nó nổi tiếng là NP-hard - tức là không hiệu quả để giải quyết nói chung.

Tuy nhiên, có tồn tại những người giải quyết tốt, cả sử dụng thương mại và miễn phí, ví dụ: trình giải mã nguồn mở lpsolve mà bạn có thể gọi từ chương trình của mình.

/EDIT: Câu trả lời cũ là giường. Tôi nhầm lẫn các yếu tố.

Answer 5

Một giải pháp tham lam sẽ làm việc Một giả:

algo(input_set , target_sum, output_set) 
    if input_set is NULL 
     error "target_sum can never be reached with all input_set" 
     return 
    the_max = maximum(input_set) 
    remove the_max from input_set 
    if the_max > target_sum 
     algo(input_set, target_sum, ouptput_set) 
     return 
    add the_max to output_set 
    algo(input_set, target_sum - the_max, output_set) 

cuộc gọi với output_set = NULL. sắp xếp intput_set để có hiệu quả.

Answer 6

Vấn đề này gần như chính xác là subset sum problem, có liên quan đến vấn đề Knapsack nhưng khác nhau và hoàn thành NP. Tuy nhiên, có một giải pháp tuyến tính nếu tất cả các số nhỏ hơn một số hằng số và một xấp xỉ thời gian Đa thức. Xem trang wikipedia được tham chiếu ở trên.

Answer 7

này trông giống như một Dynamic Programming vấn đề cổ điển (còn thể hiện bằng câu trả lời khác đề cập tương đồng so với 0-1 vấn đề Knapsack và tập hợp con Sum).Toàn bộ điều này chỉ là một lựa chọn đơn giản: đối với mỗi phần tử trong danh sách, chúng ta có sử dụng nó trong tổng của chúng ta hay không. Chúng tôi có thể viết lên một hàm đệ quy đơn giản để tính toán câu trả lời:

f(index,target_sum)= 
    0  if target_sum<=0 (i.e. we don't need to add anymore) 
    infinity if target_sum>0 and index is past the length of n (i.e. we have run out of numbers to add) 
    min(f(index+1,target_sum), f(index+1,target_sum-n[index])+n[index]) otherwise (i.e. we explore two choices - 1. take the current number 2. skip over the current number and take their minimum) 

Kể từ khi chức năng này có bài toán chồng chéo (nó khám phá những bài toán tương tự hơn và hơn nữa), nó là một ý tưởng tốt để memoize chức năng với bộ nhớ cache để giữ các giá trị đã được tính trước đó.

Dưới đây là mã trong Python:

#! /usr/bin/env python 

INF=10**9 # a large enough number of your choice 

def min_sum(numbers,index,M, cache): 
    if M<=0: # we have reached or gone past our target, no need to add any more 
     return 0 
    elif len(numbers)==index: # we have run out of numbers, solution not possible 
     return INF 
    elif (index,M) in cache: # have been here before, just return the value we found earlier 
     return cache[(index,M)] 
    else: 
     answer=min(
      min_sum(numbers,index+1,M,cache), # skip over this value 
      min_sum(numbers,index+1,M-numbers[index],cache)+numbers[index] # use this value 
     ) 
     cache[(index,M)]=answer # store the answer so we can reuse it if needed 
     return answer 

if __name__=='__main__': 
    data=[10,6,3,100] 
    M=11 

    print min_sum(data,0,M,{}) 

Giải pháp này chỉ trả về tổng mức tối thiểu, không phải là yếu tố thực tế sử dụng để thực hiện nó. Bạn có thể dễ dàng mở rộng ý tưởng để thêm ý tưởng đó vào giải pháp của mình.

Answer 8

Giải pháp tham lam hoạt động nếu câu hỏi yêu cầu số lượng mục tối thiểu. Nhưng hàm tối đa (..) sẽ tính đến khi M là âm cực đại nên trả về khoảng cách của số tới 0. (abs() của giá trị).

Hàm maximum() có thể được triển khai thông qua heap nhị phân. Độ phức tạp là O (n.logn).