Thuật toán cho việc tìm kiếm kết hợp các số nguyên lớn hơn giá trị được chỉ định

Question

Tôi đã cố gắng phát triển một thuật toán sẽ lấy một mảng đầu vào và trả về một mảng sao cho các số nguyên chứa bên trong là sự kết hợp của số nguyên với tổng nhỏ nhất lớn hơn so với giá trị được chỉ định (giới hạn đối với kết hợp kích thước k).

Ví dụ: nếu tôi có mảng [1,4,5,10,17,34] và tôi đã chỉ định số tiền tối thiểu là 31, hàm sẽ trả về [1,4,10,17]. Hoặc, nếu tôi muốn giới hạn kích thước tối đa là 2, nó sẽ chỉ trả về [34].

Có cách nào hiệu quả cách để thực hiện việc này không? Bất kỳ trợ giúp sẽ được đánh giá cao!

Answer 1

Một cái gì đó như thế này? Nó trả về giá trị, nhưng có thể dễ dàng được điều chỉnh để trả về chuỗi.

Thuật toán: giả sử đầu vào được sắp xếp, kiểm tra tổ hợp độ dài k cho tổng nhỏ nhất lớn hơn min, dừng sau phần tử mảng đầu tiên lớn hơn min.

JavaScript:

var roses = [1,4,5,10,17,34] 

function f(index,current,k,best,min,K) 
{ 
    if (roses.length == index) 
     return best 
    for (var i = index; i < roses.length; i++) 
    { 
     var candidate = current + roses[i] 
     if (candidate == min + 1) 
      return candidate 
     if (candidate > min) 
      best = best < 0 ? candidate : Math.min(best,candidate) 
     if (roses[i] > min) 
      break 
     if (k + 1 < K) 
     { 
      var nextCandidate = f(i + 1,candidate,k + 1,best,min,K) 
      if (nextCandidate > min) 
       best = best < 0 ? nextCandidate : Math.min(best,nextCandidate) 
      if (best == min + 1) 
       return best 
     } 
    } 
    return best 
} 

Output:

console.log(f(0,0,0,-1,31,3)) 
32 

console.log(f(0,0,0,-1,31,2)) 
34 

Answer 2

Đây là chi tiết của một giải pháp lai, với lập trình năng động và lại theo dõi. Chúng ta có thể sử dụng Back Tracking một mình để giải quyết vấn đề này, nhưng sau đó chúng ta phải tìm kiếm toàn bộ (2^N) để tìm ra giải pháp. Phần DP tối ưu hóa không gian tìm kiếm trong Theo dõi ngược.

import sys 
from collections import OrderedDict 
MinimumSum = 31 
MaxArraySize = 4 
InputData = sorted([1,4,5,10,17,34]) 
# Input part is over  

Target  = MinimumSum + 1 
Previous, Current = OrderedDict({0:0}), OrderedDict({0:0}) 
for Number in InputData: 
    for CurrentNumber, Count in Previous.items(): 
     if Number + CurrentNumber in Current: 
      Current[Number + CurrentNumber] = min(Current[Number + CurrentNumber], Count + 1) 
     else: 
      Current[Number + CurrentNumber] = Count + 1 
    Previous = Current.copy() 

FoundSolution = False 
for Number, Count in Previous.items(): 
    if (Number >= Target and Count < MaxArraySize): 
     MaxArraySize = Count 
     Target  = Number 
     FoundSolution = True 
     break 

if not FoundSolution: 
    print "Not possible" 
    sys.exit(0) 
else: 
    print Target, MaxArraySize 

FoundSolution = False 
Solution  = [] 

def Backtrack(CurrentIndex, Sum, MaxArraySizeUsed): 
    global FoundSolution 
    if (MaxArraySizeUsed <= MaxArraySize and Sum == Target): 
     FoundSolution = True 
     return 
    if (CurrentIndex == len(InputData) or MaxArraySizeUsed > MaxArraySize or Sum > Target): 
     return 
    for i in range(CurrentIndex, len(InputData)): 
     Backtrack(i + 1, Sum, MaxArraySizeUsed) 
     if (FoundSolution): return 
     Backtrack(i + 1, Sum + InputData[i], MaxArraySizeUsed + 1) 
     if (FoundSolution): 
      Solution.append(InputData[i]) 
      return 

Backtrack(0, 0, 0) 
print sorted(Solution) 

Lưu ý: Theo các ví dụ được đưa ra bởi bạn trong câu hỏi, tổng tối thiểu và tối đa kích thước mảng là nghiêm chỉnh hơn và ít hơn các giá trị quy định, tương ứng.

Đối với đầu vào này

MinimumSum = 31 
MaxArraySize = 4 
InputData = sorted([1,4,5,10,17,34]) 

Output là

[5, 10, 17] 

nơi như, ví đầu vào này

MinimumSum = 31 
MaxArraySize = 3 
InputData = sorted([1,4,5,10,17,34]) 

Output là

[34] 

Giải thích

Target  = MinimumSum + 1 
Previous, Current = OrderedDict({0:0}), OrderedDict({0:0}) 
for Number in InputData: 
    for CurrentNumber, Count in Previous.items(): 
     if Number + CurrentNumber in Current: 
      Current[Number + CurrentNumber] = min(Current[Number + CurrentNumber], Count + 1) 
     else: 
      Current[Number + CurrentNumber] = Count + 1 
    Previous = Current.copy() 

Phần này của chương trình phát hiện số lượng tối thiểu các số từ dữ liệu đầu vào, yêu cầu thực hiện tổng số từ 1 đến số lượng tối đa có thể (đó là tổng của tất cả các dữ liệu đầu vào). Đó là một giải pháp lập trình năng động, cho vấn đề knapsack. Bạn có thể đọc về điều đó trên internet.

FoundSolution = False 
for Number, Count in Previous.items(): 
    if (Number >= Target and Count < MaxArraySize): 
     MaxArraySize = Count 
     Target  = Number 
     FoundSolution = True 
     break 

if not FoundSolution: 
    print "Not possible" 
    sys.exit(0) 
else: 
    print Target, MaxArraySize 

Phần này của chương trình, tìm giá trị Target khớp với tiêu chí MaxArraySize.

def Backtrack(CurrentIndex, Sum, MaxArraySizeUsed): 
    global FoundSolution 
    if (MaxArraySizeUsed <= MaxArraySize and Sum == Target): 
     FoundSolution = True 
     return 
    if (CurrentIndex == len(InputData) or MaxArraySizeUsed > MaxArraySize or Sum > Target): 
     return 
    for i in range(CurrentIndex, len(InputData)): 
     Backtrack(i + 1, Sum, MaxArraySizeUsed) 
     if (FoundSolution): return 
     Backtrack(i + 1, Sum + InputData[i], MaxArraySizeUsed + 1) 
     if (FoundSolution): 
      Solution.append(InputData[i]) 
      return 

Backtrack(0, 0, 0) 

Bây giờ chúng ta biết rằng giải pháp tồn tại, chúng tôi muốn tạo lại giải pháp. Chúng tôi sử dụng kỹ thuật backtracking tại đây. Bạn có thể dễ dàng tìm thấy rất nhiều hướng dẫn tốt về điều này cũng trên internet.