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
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.
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
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
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) –