Thuật toán Knapsack với 2 thuộc tính. Làm thế nào để thực hiện điều đó trong một mảng 3D?

Question

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. Khi có 1 thuộc tính,

Tôi phải viết chương trình sử dụng thuật toán 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. Việc triển khai sai sẽ dẫn đến thời gian xử lý O (2^n). 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ơ 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.

Answer 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.

Answer 2

Để chuyển đổi từ thuật toán để giải quyết vấn đề về ba lô có hạn chế với lập trình động để giải quyết vấn đề 2 ràng buộc là rất dễ dàng. Đối với một ai đó để vẽ một hình ảnh 3d cho bạn thấy những gì đang xảy ra ở đó, tôi tưởng tượng là hơi khó. Mặt khác, thuật toán khá dễ dàng:

Giả sử bạn muốn một giải pháp chính xác, và bạn muốn giảm thiểu chi phí, không tối đa hóa giá trị (mà tôi lấy từ ví dụ của bạn). Tôi đã không thực hiện cả hai biến thể này trước đây, vì vậy tôi không thể đảm bảo không có lỗi.

1-chế

Ma trận cho bài toán xếp ba lô 1-chế là (item x weight) lưu trữ các giá trị ở mỗi vị trí.

Thuật toán về cơ bản là:

// WL = backpack weight limit 
A[0, 0] = 0 
for w = 1, 2, ..., WL // weight 
    A[0, w] = INFINITY 
for i = 1, 2, ..., n // items 
    for w = 0, 1, ..., WL // weight 
    // wi and ci are the weight and cost of the item respectively 
    // A[i-1, w-wi] + ci = 0 when wi > w 
    A[i, w] = min(A[i-1, w], A[i-1, w-wi] + ci) 

2-chế

Bây giờ mở rộng này để bao gồm hạn chế khác chỉ là: (giả sử size là trở ngại khác)

Ma trận sẽ là (item x weight x size).

// WL = backpack weight limit 
// SL = backpack size limit 
for w = 0, 1, ..., WL // weight 
    for s = 0, 1, ..., SL // size 
    A[0, w, s] = INFINITY 
A[0, 0, 0] = 0 
for i = 1, 2, ..., n // items 
    for w = 0, 1, ..., WL // weight 
    for s = 0, 1, ..., SL // size 
     // wi, si and ci are the weight, size and cost of the item respectively 
     // A[i-1, w-wi, s-si] + ci = 0 when wi > w or si > s 
     A[i, w, s] = min(A[i-1, w, s], A[i-1, w-wi, s-si] + ci)