động Lập trình và Ứng dụng Knapsack

Question

Im học lập trình năng động và đang tìm cách để giải quyết vấn đề sau đây, có thể được tìm thấy ở đây http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf:

Bạn đang đưa ra một mảnh hình chữ nhật của vải với kích thước X của Y, trong đó X và Y là các số nguyên dương và danh sách các sản phẩm n có thể được thực hiện bằng cách sử dụng vải. Đối với mỗi sản phẩm i trong [1, n] bạn biết rằng một hình chữ nhật có kích thước bằng bi là cần thiết và giá bán cuối cùng của sản phẩm là ci. Giả sử rằng ai, bi và ci là tất cả các số nguyên dương. Bạn có một chiếc máy có thể cắt bất kỳ miếng vải hình chữ nhật nào thành hai mảnh theo chiều ngang hoặc chiều dọc. Thiết kế một thuật toán tìm ra chiến lược tốt nhất để cắt miếng vải X của Y để các sản phẩm được tạo ra từ các mảnh kết quả tạo ra tổng giá bán tối đa. Bạn được tự do tạo ra nhiều bản sao của một sản phẩm nhất định như bạn muốn, hoặc không có sản phẩm nào nếu muốn. (Từ các thuật toán của Dasgupta, Papadimitriou, và Vazirani.)

Có vẻ như chúng ta có vấn đề về ba lô hai chiều, nhưng tôi nghĩ có thể giải quyết nó bằng thuật toán ba lô truyền thống bằng cách xem xét trọng lượng như các khu vực của hình chữ nhật. Điều này có vẻ giống như một cách tiếp cận hợp lý?

Đây là một bài tập lập trình cho một khóa học tôi đang dùng vì vậy xin vui lòng chỉ bao gồm thảo luận khái niệm và/hoặc mã giả để minh họa ý tưởng.

Answer 1

Tôi nghĩ bạn nên tập trung vào thực tế là máy cắt vải thành hai phần. Những gì có thể phù hợp với mỗi một trong hai phần đó? Hãy xem xét những điều sau đây:

+-------------+-------------------+ 
|    |  Piece B  | 
|    |     | 
| Piece A +----------+--------+ 
|    |   |  | 
|    |   |  | 
|    |   | Piece | 
+-------------+----------+ C | 
|      |  | 
|   Piece D  |  | 
+------------------------+--------+ 

Bốn thứ này trong vải, nhưng không theo cách có thể đạt được với ba lần cắt. (Có thể một sự sắp xếp khác sẽ cho phép điều đó với những phần đặc biệt này, nghĩ về điều này như là một sơ đồ khái niệm, không phải để mở rộng quy mô. Các kỹ năng nghệ thuật ascii của tôi bị giới hạn ngày hôm nay.)

Tập trung vào "cắt ở đâu" sẽ cung cấp cho bạn giải pháp lập trình động. Chúc may mắn.

Answer 2

Vì vậy, bạn bắt đầu với hình chữ nhật X * Y. Giả sử giải pháp tối ưu liên quan đến việc cắt ngang (hoặc ngang), sau đó bạn có hai hình chữ nhật mới có kích thước X * Y1 và X * Y2 với Y1 + Y2 = Y. Vì bạn muốn tối đa hóa lợi nhuận, bạn cần tối đa hóa lợi nhuận trên các hình chữ nhật mới này (cấu trúc con tối ưu). Vì vậy, đệ quy ban đầu của bạn như sau: f(X, Y) = max(f(X, Y1) + f(X, Y2), f(X1, Y) + f(X2, Y)) cho tất cả các giá trị posible của X1, X2 (cắt ngang) và Y1, Y2 (cắt dọc).

Bây giờ câu hỏi là khi nào tôi thực sự quyết định tạo một sản phẩm? Bạn có thể quyết định tạo ra một sản phẩm khi một trong các kích thước của nó bằng một trong các kích thước của hình chữ nhật hiện tại của bạn (tại sao? Bởi vì nếu điều này không giữ, và giải pháp tối ưu bao gồm tạo ra sản phẩm này, sớm thì muộn bạn sẽ cần thực hiện cắt ngang (hoặc nằm ngang) và trường hợp này đã được xử lý trong đệ quy ban đầu), do đó bạn thực hiện cắt thích hợp và bạn có hình chữ nhật mới X * Y1 (hoặc X1 * Y), tùy thuộc vào việc cắt bạn đã thực hiện để lấy sản phẩm), trong trường hợp này, đệ quy trở thành f(X, Y) = cost of product + f(X1, Y).

Giải pháp của vấn đề ban đầu là f(X, Y). Thời gian chạy của giải pháp dp này là O(X * Y * (X + Y + number of available products)): bạn có X * Y hình chữ nhật có thể, cho mỗi hình này bạn thử mọi cắt có thể (X + Y) và bạn cố gắng làm cho một trong các sản phẩm sẵn có ra khỏi hình chữ nhật này.

Ngoài ra, hãy xem sự cố tương tự này: Chia sẻ sô cô la từ vòng chung kết thế giới ICPC 2010.

Answer 3

Vui lòng bao gồm các điều kiện cần thiết cho hình chữ nhật có kích thước (0, something) hoặc (something, 0) trong chức năng Rect().

Answer 4

optimize() {

Rectangle memo[width][height] 
optimize(0,0,totalwidth, totalheight, memo) 

}

optimize (x, y, width, height, ghi nhớ) {

if memo[width][height] != null 
    return memo[width][height] 

rect = new Rectangle(width, height, value = 0) 
for each pattern { 

    //find vertical cut solution 
    leftVerticalRect = optimize (x, y + pattern.height, pattern.width, height-pattern.height,memo) 
    rightVerticalRect = optimize(x + pattern.width, y, width-pattern.width, height) 
    verticalcut = new Cut(x + pattern.width, y, x + pattern.width, y + height) 

    //find horizontal cut solution 
    topHorizontalRect = optimize (--parameters--) 
    bottomHortizonalRect = optimize(--parameters--) 
    horizontalcut = new Cut(--parameters--) 

    //see which solution is more optimal 
    if (leftVerticalRect.val + rightVerticalRect.val > topHorizontalRect.val + bottomHorizontalRect.val) 
     subprobsolution = vertical cut solution 
    else 
     subprobsolution = horizontal cut solution 

    //see if the solution found is greater than previous solutions to this subproblem 
    if (subprobsolution.value + pattern.value > rect.value) { 
     rect.subrect1 = subprobsolutionrect1 
     rect.subrect2 = subprobsolutionrect2 
     rect.pattern = pattern 
     rect.cut = subprobsolutioncut 
     rect.value = rect.subrect1.value + rect.subrect2.value + rect.pattern.value 
    } 
} 

memo[width][height] = rect 
return rect 

}