Loại thuật toán nào? (Knapsack, Bin đóng gói !?)

Question

Vấn đề là như sau:

Bạn đã n vấp dài trong km mà phải được chia cho các số m ngày như vậy mà số tiền tối đa độ dài mỗi ngày được giảm thiểu. Ví dụ. Độ dài chuyến đi [1,5,2,6,8,3,2] chia cho 3 ngày dẫn đến [1,5,2] [6] [8,3,2] vì tổng số tiền dài tối đa là mức thấp nhất chúng ta có thể đạt được.

Có một loại thuật toán mô tả cách xử lý sự cố như vậy không? Tôi đã xem xét việc đóng gói thùng rác và vấn đề về chiếc ba lô, nhưng không có vấn đề nào trong số đó bao gồm vấn đề của tôi. Tôi có thể tưởng tượng nó có thể là một chút sửa đổi của bao bì bin nhưng không đi đến kết luận.

Answer 1

Vấn đề này có thể được giải quyết bằng Binary Search

Giả sử rằng độ dài tối đa là X, chúng ta có thể dễ dàng kiểm tra nếu chúng ta có thể chia các chuyến đi vào ngày m với chiều dài tối đa cho mỗi ngày là không lớn hơn X của thành viên này sau tham lam:

boolean isValid(int X){ 
    int currentLength = 0; 
    int numberOfDays = 1; 
    for(int i = 0; i < n; i++) 
     if (trip[i] > X) 
     return false; 
     if(currentLength + trip[i] <= X){ 
     currentLength += trip[i]; 
     }else{ 
     currentLength = trip[i]; 
     numberOfDays++; 
     } 
    } 
    return numberOfDays <= m; 
} 

sau đó, chúng ta có thể dễ dàng tìm được tối thiểu đối với X bởi việc tìm kiếm nhị phân sau:

int start = 0; 
int end = sum of all trips; 
int result = end; 
while(start <=end){ 
    int mid = (start + end)/2; 
    if(isValid(mid)){ 
     result = mid; 
     end = mid - 1; 
    }else{ 
     start = mid + 1; 
    } 
} 

Độ phức tạp thời gian là O (n log z) với z là tổng của tất cả các chuyến đi.

Answer 2

Nó có thể được giải quyết bằng cách sử dụng phương pháp lập trình động nơi trạng thái được xác định là DP[i][j] trong đó i là chỉ số kết thúc của ngày và j giữ số ngày cho đến thời điểm này. Bạn có thể chuyển sang trạng thái tiếp theo và lấy số tiền tối đa của một ngày tương ứng với chuyển động hiện tại và sau đó có thể so sánh nó với mức tối thiểu chung.

Tôi đã viết giải pháp lập trình động đệ quy trong C++, có thể hơi khó hiểu về cách chuyển tiếp trạng thái hoạt động mà bạn có thể cần xem xét Lập trình động với memoisation để hiểu nó.

#include <iostream> 
#define INF 1000000000 
using namespace std; 

int n, m, dist[100] = {1,5,2,6,8,3,2}, dp[1000][1000]; 

int solve(int index, int count){ 
    if(index == n){ 
     if(count == m) return 0; 
     else return INF; 
    } 
    if(dp[index][count] != -1) return dp[index][count]; 
    int sum = 0, ans = INF; 
    for(int i = index;i < n;i++){ 
     sum += dist[i]; 
     int val = max(sum, solve(i+1, count+1)); 
     ans = min(ans, val); 
    } 
    return dp[index][count] = ans; 
} 

int main() { 
    // your code goes here 
    n = 7, m = 3; 
    for(int i = 0;i < 1000;i++) for(int j = 0;j < 1000;j++) dp[i][j] = -1; 
    cout << solve(0, 0) << endl; 
    return 0; 
} 

Liên kết với giải pháp Ideone: https://ideone.com/glHsgF

Answer 3

Nó không Knapsack cũng không Bin đóng gói. Đó là tên thường gặp là vấn đề phân vùng k.
Như đã đề cập trong các ý kiến, điều này có thể được thực hiện bằng cách sử dụng lập trình động.

DP[N,M] - minimum cost of partitioning the array = {a1, ... , aN} into M partitions. 
      Where cost is defined as the maximum sum of each partition. 
DP[1,m] = a1 
DP[n,1] = Sum of all elements in the array {a1, ... , an} 
DP[n,m] = min over k from 1 to n (max(DP[n-k,m-1],sum of elements n-k to n))