2012-11-19 14 views
12

Khi có 1 thuộc tính, tôi hiểu những gì đang diễn ra trong đó. Tôi đang gặp sự cố khi hiểu vấn đề về ba lô khi có nhiều hơn 1 thuộc tính.Thuật toán Knapsack với thuộc tính bổ sung

enter image description here

tôi phải viết một chương trình có sử dụng thuật toán xếp ba lô với 2 thuộc tính. Sư phụ nói với chúng tôi, Nó phải được thực hiện trong một mảng 3D. Tôi không thể tưởng tượng như thế nào mảng như vậy sẽ như thế nào.

Hãy nói rằng đây là đầu vào của tôi:

4 3 4 // number of records below, 1st property of backpack, 2nd property of backpack 
1 1 1 // 1st property, 2nd property, cost 
1 2 2 // 1st property, 2nd property, cost 
2 3 3 // 1st property, 2nd property, cost 
3 4 5 // 1st property, 2nd property, cost 

Và đầu ra sẽ trông như thế:

4 // the cheapest sum of costs of 2 records 
1 3 // numbers of these 2 records 

Lời giải thích của đầu ra: 2 bộ hồ sơ phù hợp của thành dòng 1'st đầu vào :

(1) - bản ghi số 1 và số bản ghi 3

1 1 1 
+ 2 3 3 
------- 
    3 4 4 

(2) - con số kỷ lục 4

3 4 5 

Bởi vì bộ 1 của hồ sơ là rẻ nhất (4 < 5), chúng tôi đã chọn nó. Không chỉ tôi sẽ phải tìm hiểu xem liệu bộ hồ sơ đó có tồn tại hay không, tôi cũng sẽ phải tìm các hồ sơ mà tôi đã tổng kết.

Nhưng hiện tại, tôi chỉ cần hiểu, mảng 3D sẽ trông như thế nào. Có thể một số bạn giúp tôi với điều đó và hiển thị, từng lớp, giống như trong hình ảnh của tôi, làm thế nào sẽ như thế này? Cảm ơn.

enter image description here

+0

Tôi không chắc tôi hiểu mảng đầu tiên của bạn. Ý nghĩa của các giá trị trong mảng là gì? – gmlobdell

+0

ví dụ: Trong ba lô với V = 2 và 1 2 mặt hàng với V = 1, bạn có thể đặt tối đa 2x V = 1 mục. Trong ba lô với V = 3, và với các mặt hàng V = 1 và V = 1, bạn có thể đặt ở đó tối đa cả hai mục này để nó v = 2 bên trong ô đó. Trong ba lô với v = 3 và các mặt hàng 1,1,2, bạn có thể đặt tối đa 2 mặt hàng (v = 1, v = 2) do đó nó mang lại cho 3. Giá trị bên trong các ô là gói tối đa của ba lô – Paulina

+3

Tôi nghĩ rằng bạn giáo viên tìm kiếm [nhiều vấn đề ràng buộc knapsack] (http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints) –

Trả lời

1

Bạn đang cố gắng làm điều gì đó không thể - đó là vấn đề của bạn.

Khi bạn thêm số thứ nguyên, các mục của bạn sẽ nhận được các thuộc tính bổ sung. Vì vậy, thay vì bên trái, cột của một bảng (prop1), bạn có cạnh hình chữ nhật (prop1 x prop2) hoặc chặn bên (prop1 x prop2 x prop3) v.v. Nhưng các ràng buộc hiện tại, xác định phía trên, hàng của bảng, phải có cùng số thứ nguyên. Không chỉ một chiều!. Vì vậy, bạn sẽ không bao giờ có thể đặt vấn đề hai thuộc tính vào khối 3 chiều, bạn cần khối 4D thay thế. 6D khối cho 3 tài sản và như vậy.

+0

Bạn có thể giải thích "tính chất bổ sung" là gì? Bảng là để ghi lại cấu hình tốt nhất của ba lô cho một chi phí. Có vẻ như bạn đang suy nghĩ khác đi. – dragonxlwang

1

Giả sử bạn đang sử dụng một bảng ba chiều: A[x][y][z]=k, x: tổng hợp thuộc tính thứ nhất; y: tổng tài sản thứ 2; z: tổng tài sản thứ 3; k: chi phí tối thiểu (phần thưởng tối đa mà tôi muốn sử dụng phần thưởng)

Vì vậy, bạn lặp qua các mục. Nói mục hiện tại là (p1, p2, p3, phần thưởng) (phần thưởng = - chi phí).cho mỗi (x,y,z,k), công thức cập nhật của bạn:

A[x+p1][y+p2][z+p3] = max(A[x+p1][y+p2][z+p3], A[x+p1][y+p2][z+p3] + reward) 

Nếu hạn 1 trên RHS lớn, trên khe A[x+p1][y+p2][z+p3], cấu hình của chiếc ba lô là vẫn còn; nếu không, bạn cập nhật các knapsack theo đó là A[x+p1][y+p2][z+p3] cộng với mục hiện tại.

Hy vọng điều này sẽ rõ ràng.