Thuật toán lập kế hoạch công việc trong Java

Question

Tôi cần phải thiết kế một thuật toán hiệu quả cho một vấn đề lập kế hoạch và tôi thực sự không có một đầu mối.

Có một máy sản xuất thuốc theo một tỷ lệ nhất định. Ví dụ, máy có thể sản xuất 1 viên nếu nó được phép làm việc liên tục trong một ngày, 4 viên, nếu được phép làm việc trong 3 ngày, 16 viên nếu nó hoạt động trong 5 ngày, v.v. Nếu tôi ngừng máy và lấy tất cả các viên thuốc thì máy sẽ bắt đầu lại từ ngày thứ 1. Tất cả các viên thuốc mà tôi lấy ra từ máy phải được sử dụng trong cùng một ngày.

Có một số lượng bệnh nhân nhất định đến và uống thuốc mỗi ngày. Các bệnh nhân phải được điều trị trong cùng một ngày, bệnh nhân không được điều trị được bỏ qua. Mục tiêu là quyết định ngày nào sẽ dừng máy và điều trị càng nhiều bệnh nhân càng tốt trong n ngày.

Giả sử số ngày n = 5, được đưa ra ví dụ đầu vào

int[] machineRate = {1,2,4,8,16}; 
int[] patients = {1,2,3,0,2}; 

Trong trường hợp này, nếu tôi dừng máy vào ngày thứ 3, tôi sẽ có 4 viên thuốc. Tôi có thể điều trị 3 bệnh nhân và vứt bỏ 1 viên thuốc. Sau đó, tôi ngừng máy vào ngày thứ 5 một lần nữa, vì nó đã được dừng lại vào ngày thứ 3, nó đã được làm việc trong 2 ngày, do đó tôi có 2 viên thuốc để điều trị cho 2 bệnh nhân. Vào cuối 3 + 2 = 5, đầu ra = 5 bệnh nhân.

Nếu tôi dừng máy vào ngày 2, ngày 3, ngày 5. Sau đó, đầu ra sẽ là (2 viên cho 2 bệnh nhân vào ngày thứ 2) + (1 viên cho 3 bệnh nhân vào ngày thứ 3) + （2 viên thuốc 2 bệnh nhân vào ngày thứ 5）. Điều đó tương đương với 5 bệnh nhân.

machineRate[] và patients[] thay đổi theo đầu vào.

Thuật toán tìm số lượng bệnh nhân được điều trị tối đa là gì?

Answer 1

Đây là một vấn đề lập trình động tuyệt vời.

Cách suy nghĩ của quy hoạch động là tự hỏi mình hai câu hỏi:

1. Có một phiên bản tầm thường của vấn đề này nếu tôi giảm một (hoặc nhiều) của các biến số không (hoặc tương tự)?
2. Có cách đơn giản nào để tính câu trả lời cho vấn đề có kích thước n+1 nếu tôi biết câu trả lời cho tất cả các vấn đề về kích thước n? (Ở đây, "kích thước" là vấn đề cụ thể và bạn cần phải tìm đúng khái niệm về kích thước giúp giải quyết vấn đề trong tay.)

Đối với vấn đề này, phiên bản tầm thường là gì? Vâng, giả sử số ngày là 1. Sau đó, nó sẽ được dễ dàng: Tôi dừng máy, và điều trị càng nhiều bệnh nhân càng tốt. Không có điểm nào làm bất cứ điều gì khác.

Bây giờ, nếu chúng ta xem xét số ngày còn lại như khái niệm về kích thước của chúng tôi, chúng tôi cũng nhận được câu trả lời cho câu hỏi thứ hai. Giả sử chúng ta biết tất cả các câu trả lời cho tất cả các sự cố khi còn lại n ngày. Hãy viết maxTreat(days, running) cho số lượng tối đa mà chúng tôi có thể xử lý nếu có days ngày còn lại và nếu máy đã chạy ban đầu trong running ngày.

Hiện tại có n+1 ngày còn lại; và máy đã chạy cho đến nay trong k ngày. Chúng tôi có hai lựa chọn: (1) dừng máy; (2) không dừng lại.Nếu chúng ta dừng máy, chúng ta có thể điều trị một số bệnh nhân ngày hôm nay (chúng ta có thể tính số lượng dựa trên k), và sau đó chúng ta có thể điều trị bệnh nhân maxTreat(n, 1), vì sau đó có n ngày còn lại, và vào ngày mai máy sẽ hoạt động trở lại chỉ trong một ngày. Nếu chúng tôi không dừng máy, chúng tôi không thể đối xử với bất cứ ai hôm nay, nhưng sau đó chúng tôi sẽ có thể điều trị maxTreat(n,k+1) bệnh nhân, bởi vì vào ngày mai máy sẽ hoạt động trong k+1 ngày.

Tôi sẽ để bạn giải thích chi tiết chính xác, nhưng để giải quyết hiệu quả, chúng tôi tạo một mảng đa chiều, dựa trên số ngày còn lại và số ngày mà máy đã chạy từ trước đến nay. Sau đó chúng tôi lặp qua mảng, giải quyết tất cả các vấn đề có thể xảy ra, bắt đầu từ tầm thường (một ngày còn lại) và làm việc ngược (hai ngày, sau đó ba ngày, v.v.). Ở mỗi giai đoạn, vấn đề chúng ta đang giải quyết hoặc là tầm thường (vì vậy chúng ta chỉ có thể viết câu trả lời), hoặc một cái gì đó chúng ta có thể tính toán từ các mục chúng ta đã viết vào mảng ở bước trước.

Điều thực sự thú vị về lập trình động là chúng tôi đang tạo bộ nhớ cache của tất cả các kết quả khi chúng tôi thực hiện. Vì vậy, đối với các vấn đề mà một cách tiếp cận đệ quy nếu không sẽ cần phải tính toán câu trả lời cho một vấn đề phụ nhiều lần, với lập trình động, chúng ta không bao giờ kết thúc giải quyết một vấn đề phụ nhiều hơn một lần.

ý kiến ​​bổ sung bây giờ mà tôi đã nhìn thấy thực hiện của bạn:

Đối với một, tôi không quá ngạc nhiên khi nó bắt đầu chậm lại khi bạn nhấn 10.000 hoặc lâu hơn. Thuật toán là O(n^2), bởi vì tại mỗi lần lặp, bạn phải điền vào mảng với tối đa n mục trước khi bạn có thể chuyển sang cấp độ tiếp theo. Tôi khá chắc chắn rằng O(n^2) là sự phức tạp tiệm cận tốt nhất bạn sẽ nhận được cho câu đố này, mặc dù.

Nếu bạn muốn tăng tốc thêm, bạn có thể xem cách tiếp cận từ trên xuống. Hiện tại bạn đang thực hiện lập trình động từ dưới lên: giải quyết các trường hợp có kích thước 0, sau đó là kích thước 1, v.v. Nhưng bạn cũng có thể làm theo cách khác. Về cơ bản đây là thuật toán tương tự như khi bạn đang viết một giải pháp đệ quy không hiệu quả khủng khiếp để tính toán các giải pháp cho các vấn đề phụ khi đang bay, ngoại trừ việc bạn lưu lại kết quả mỗi khi bạn tính toán nó. Vì vậy, nó trông giống như thế này:

1. Thiết lập mảng hai chiều của bạn để giữ các giải pháp cho các vấn đề phụ. Điền sẵn với -1 cho mỗi trường hợp. Giá trị -1 sẽ cho biết bạn chưa giải quyết được vấn đề phụ đó.
2. Viết thói quen giải quyết maxTreat(days, running) về câu trả lời cho các vấn đề phụ ở cấp độ tiếp theo. Khi bạn muốn câu trả lời cho các vấn đề phụ, hãy tìm trong mảng. Nếu có -1 trong đó, bạn vẫn chưa giải quyết câu trả lời đó, vì vậy bạn đệ quy giải quyết nó, và sau đó đặt câu trả lời vào mảng. Nếu có bất kỳ điều gì khác hơn -1, bạn chỉ có thể sử dụng giá trị bạn tìm thấy ở đó, bởi vì bạn đã tính toán nó. (Bạn cũng có thể sử dụng một số HashMap thay vì mảng đa chiều.)

Điều này tốt hơn theo cách này và tệ hơn trong cách khác. Nó tồi tệ hơn bởi vì bạn có overheads kết hợp với đệ quy, và bởi vì cuối cùng bạn sẽ chạy ra khỏi stack với các cuộc gọi đệ quy. Bạn có thể cần phải tăng kích thước ngăn xếp với tham số dòng lệnh cho JVM.

Nhưng tốt hơn trong một khía cạnh quan trọng: bạn không tính câu trả lời cho tất cả các sự cố phụ, nhưng chỉ những vấn đề bạn cần biết câu trả lời. Đối với một số vấn đề, đó là một sự khác biệt lớn, và đối với một số, nó không phải. Thật khó để có được trực giác đúng, nhưng tôi nghĩ nó có thể tạo nên sự khác biệt lớn ở đây. Xét cho cùng, mỗi câu trả lời chỉ phụ thuộc vào hai vấn đề phụ từ hàng trước.

Giải pháp cuối cùng (không thử điều này cho đến khi bạn nhận được từ trên xuống đệ quy đi đầu tiên!) Là để làm điều đó từ trên xuống nhưng không có đệ quy. Điều này sẽ tránh được vấn đề về không gian ngăn xếp. Để làm điều này, bạn tạo một chồng các vấn đề phụ (sử dụng một số ArrayDeque) cần giải quyết, và bạn tiếp tục đưa chúng ra khỏi hàng đợi cho đến khi không còn hàng. Điều đầu tiên là đẩy vào ngăn xếp vấn đề lớn mà bạn cần một giải pháp. Bây giờ, bạn lặp đi lặp lại các vấn đề bật ra khỏi ngăn xếp cho đến khi nó trống. Bật một lần, và gọi nó là P. Sau đó:

1. Tìm trong mảng của bạn hoặc HashMap để xem nếu P đã được giải quyết chưa. Nếu có, hãy trả lời câu trả lời.
2. Nếu không, hãy tìm hiểu xem các sự cố phụ cho P đã được giải quyết chưa. Nếu họ có, sau đó bạn có thể giải quyết P và bạn lưu trữ câu trả lời. Nếu ngăn xếp giờ trống, thì bạn đã giải quyết được vấn đề cuối cùng của mình và bạn trả lời cho P.
3. Nếu các vấn đề phụ chưa được giải quyết xong, hãy đẩy P trở lại ngăn xếp. Sau đó đẩy bất kỳ vấn đề phụ của P mà chưa được giải quyết vào ngăn xếp là tốt.

Điều gì sẽ xảy ra khi bạn đi là ngăn xếp của bạn sẽ phát triển ban đầu khi bạn đẩy vấn đề chính, và các vấn đề phụ của nó, và sau đó vấn đề phụ của nó, vào ngăn xếp. Sau đó, bạn sẽ bắt đầu giải quyết các trường hợp nhỏ hơn và đưa kết quả vào bộ nhớ cache, cho đến khi cuối cùng bạn có mọi thứ bạn cần để giải quyết vấn đề chính.

Nó không sử dụng bộ nhớ ít hơn đáng kể so với phương pháp đệ quy từ trên xuống, nhưng nó sử dụng không gian heap thay vì không gian chồng JVM, và điều đó có nghĩa là nó tăng lên tốt hơn vì chồng JVM nhỏ hơn nhiều so với đống.

Điều này khá khó khăn. Ít nhất, hãy giữ giải pháp làm việc của bạn trước khi bạn bắt đầu mã hóa phiên bản khó khăn hơn!

Answer 2

Một cách tiếp cận khác là dự đoán ngày hoặc ngày tiếp theo. Giả sử chúng ta đã thấy 1,2.patients trong những ngày cuối cùng, chúng ta có thể uống hai viên thuốc ngày hôm nay và chữa trị hai bệnh nhân hoặc dự đoán ba hoặc nhiều hơn cho ngày hôm sau và để máy chạy. Nếu chúng tôi không tăng lên như 1,1, chúng tôi sẽ dự đoán một bệnh nhân cho ngày mai và uống một viên thuốc ngày hôm nay. Nếu ngày hôm sau hóa ra khác nhau như 1, 4, 0, chúng ta chỉ cần điều chỉnh dự đoán cho ngày hôm sau là 1/2, tức là 2. Phía trên của giải pháp này là bạn có thể làm việc với sự không chắc chắn, tức là bạn không biết những gì ngày mai mang lại. điều này cho phép chúng tôi truyền dữ liệu. Down side là bệnh nhân đầu tiên sẽ luôn luôn chết.

Answer 3

Tôi đã triển khai thiết kế của chi-an ninh, nhưng hiệu suất không tuyệt vời khi n lớn hơn 10000 hoặc hơn. Nếu bất cứ ai có bất kỳ ý tưởng khác xin vui lòng cho tôi biết vì tôi nghĩ rằng đây là một vấn đề khá thú vị. Tôi đã thử nó với đệ quy lúc đầu nhưng vẫn tiếp tục chạy ra khỏi bộ nhớ, vì vậy tôi đã phải làm điều đó trong một vòng lặp thay thế. Tôi đã lưu trữ một mảng 2d lớn với tất cả kết quả cho đến nay nhưng sau đó tôi nhận ra rằng tôi chỉ cần truy cập "hàng" trước đó của kết quả vì vậy tôi chỉ sử dụng 2 mảng: "hiện tại" và "trước đó":

static int calculateMax() { 
    int[] previous = new int[n]; 
    for (int daysMachineRunning=0; daysMachineRunning<n; daysMachineRunning++) { 
     previous[daysMachineRunning] = treatPatients(0, daysMachineRunning); 
    } 

    int[] current = null; 
    for (int daysRemaining=1; daysRemaining<n; daysRemaining++) { 
     current = new int[n-daysRemaining]; 
     for (int daysMachineRunning=0; daysMachineRunning<n-daysRemaining; daysMachineRunning++) { 
      current[daysMachineRunning] = Math.max(
        treatPatients(daysRemaining, daysMachineRunning) + previous[0], 
        previous[daysMachineRunning+1] 
       ); 
     } 
     previous = current; 
    } 
    return current[0]; 
} 

static int treatPatients(int daysRemaining, int daysMachineRunning) { 
    return Math.min(patients[n-1-daysRemaining], machineRate[daysMachineRunning]); 
} 

EDIT: Tôi hiện đã triển khai phương pháp tiếp cận thứ 2 nhưng vẫn gặp sự cố trong đó n> = 10000 hoặc hơn: Exception in thread "main" java.lang.OutOfMemoryError: Java heap space. Đây là mã của tôi nếu bất kỳ ai quan tâm đến việc theo đuổi thêm:

static final int[][] results = new int[n][n]; 
static final SortedSet<Target> queue = new TreeSet<>(new Comparator<Target>() { 
    @Override 
    public int compare(Target o1, Target o2) { 
     if (o1.daysRemaining < o2.daysRemaining) 
      return -1; 
     else if (o1.daysRemaining > o2.daysRemaining) 
      return 1; 
     else if (o1.daysMachineRunning < o2.daysMachineRunning) 
      return 1; 
     else if (o1.daysMachineRunning > o2.daysMachineRunning) 
      return -1; 
     else return 0; 
    } 
}); 

public static void main(String[] args) { 
    for (int i=0; i<n; i++) { 
     Arrays.fill(results[i], -1); 
    } 

    if (n <= 10) { 
     System.out.println(Arrays.toString(machineRate)); 
     System.out.println(Arrays.toString(patients)); 
    } else 
     System.out.println(n); 

    System.out.println(calculateMax()); 
} 

static class Target { 
    int daysRemaining, daysMachineRunning; 
    Target(int daysRemaining, int daysMachineRunning) { 
     this.daysRemaining = daysRemaining; 
     this.daysMachineRunning = daysMachineRunning; 
    } 
} 

static int calculateMax() { 
    addTarget(n-1, 0); 
    while (results[n-1][0]==-1) { 
     Target t = queue.first(); 
     queue.remove(t); 
     calculateMax(t); 
    } 
    return results[n-1][0]; 
} 

static void calculateMax(Target t) { 
    int daysRemaining = t.daysRemaining; 
    int daysMachineRunning = t.daysMachineRunning; 
    int treatedPatients = Math.min(patients[n-1-daysRemaining], machineRate[daysMachineRunning]); 
    if (daysRemaining==0) 
     results[0][daysMachineRunning] = treatedPatients; 
    else { 
     int resultA = results[daysRemaining-1][0]; 
     int resultB = results[daysRemaining-1][daysMachineRunning+1]; 
     if (resultA>=0 && resultB>=0) { 
      results[daysRemaining][daysMachineRunning] = Math.max(treatedPatients + resultA, resultB); 
     } 
     else { 
      if (resultA==-1) 
       addTarget(daysRemaining-1, 0); 
      if (resultB==-1) 
       addTarget(daysRemaining-1, daysMachineRunning+1); 
      addTarget(daysRemaining, daysMachineRunning); 
     } 
    } 
} 

static void addTarget(int a, int b) { 
    queue.add(new Target(a,b)); 
}