Bất kỳ thuật toán đa thức giả nào cho bít đa khớp 0-1 bị chặn?

Question

Giả sử rằng có n mặt hàng, ví dụ như tôi , tôi , .... i _n, mỗi người trong số họ với một trọng lượng bị chặn gọi w , w ... w _n. Ngoài ra còn có một tập hợp các gói ba lô, ví dụ: k , k và k _m. Ba lô là đồng nhất, rằng tất cả chúng đều có cùng công suất W. Hàm F có thể xác định số điểm của mỗi chiếc ba lô. Các yếu tố đầu vào của F là các mục trong mỗi chiếc ba lô. Vì vậy,

Score of each knapsack i = F(Items in knapsack i) 

Bây giờ tôi muốn đặt một số mặt hàng trong ba lô theo cách như vậy mà:

1. Trọng lượng của các mục trong một ba lô không vượt quá khả năng của mình W.
2. Tổng điểm số cho tất cả ba lô là tối đa

Có giải pháp thời gian đa thức cho vấn đề này hay không?

Lưu ý: Vấn đề là 0-1, đó là mỗi mục có thể được chọn hay không. Tất cả các thông số vấn đề đều bị giới hạn.

Chỉnh sửa 1: Không thể giảm sự cố này để đóng gói thùng rác và sau đó kết luận rằng đó là sự cố NP-hard?

Chỉnh sửa 2 Trong vấn đề này, mỗi mục có ba thuộc tính, ví dụ: các thuộc tính a _i, b _i và c _i. Hàm F là hàm tuyến tính nhận các thuộc tính của các mục bên trong nó và tạo ra kết quả đầu ra.

Edit3: Có vẻ như this paper đã đề xuất giải pháp chính xác cho vấn đề đa khớp. Nó có thể được sử dụng trong trường hợp của tôi?

Answer 1

Làm thế nào về điều này?

Cho một giải pháp năng động tiêu chuẩn trong Haskell cho một vấn đề 0-1 ba lô, tìm thấy here,

inv = [("map",9,150), ("compass",13,35), ("water",153,200), ("sandwich",50,160), 
     ("glucose",15,60), ("tin",68,45), ("banana",27,60), ("apple",39,40), 
     ("cheese",23,30), ("beer",52,10), ("cream",11,70), ("camera",32,30), 
     ("tshirt",24,15), ("trousers",48,10), ("umbrella",73,40), 
     ("trousers",42,70), ("overclothes",43,75), ("notecase",22,80), 
     ("sunglasses",7,20), ("towel",18,12), ("socks",4,50), ("book",30,10)] 

knapsack = foldr addItem (repeat (0,[])) where 
    addItem (name,w,v) list = left ++ zipWith max right newlist where 
     newlist = map (\(val, names)->(val + v, name:names)) list 
     (left,right) = splitAt w list 

main = print $ (knapsack inv) !! 400 

chúng ta thêm một cơ chế nhồi nhét, đặt các hoán vị hàng tồn kho liên tục trong ba lô tiếp theo mà có không gian,

stuff (name,w,v) left (v2,[]) = (v2,left) 
stuff (name,w,v) left (v2,(cap, lst):xs) = 
    if w <= cap 
    then (v + v2, left ++ [(cap - w, (name,w,v):lst)] ++ xs) 
    else stuff (name,w,v) (left ++ [(cap,lst)]) (v2,xs) 

và thay thế nó cho hàm được ánh xạ. Đưa nó tất cả cùng nhau:

inv = [("map",9,150), ("compass",13,35), ("water",153,200), ("sandwich",50,160), 
     ("glucose",15,60), ("tin",68,45), ("banana",27,60), ("apple",39,40), 
     ("cheese",23,30), ("beer",52,10), ("cream",11,70), ("camera",32,30), 
     ("tshirt",24,15), ("trousers",48,10), ("umbrella",73,40), 
     ("trousers",42,70), ("overclothes",43,75), ("notecase",22,80), 
     ("sunglasses",7,20), ("towel",18,12), ("socks",4,50), ("book",30,10)] 

capacity = 200::Int 
numKnapsacks = 3 

stuff (name,w,v) left (v2,[]) = (v2,left) 
stuff (name,w,v) left (v2,(cap, lst):xs) = 
    if w <= cap 
    then (v + v2, left ++ [(cap - w, (name,w,v):lst)] ++ xs) 
    else stuff (name,w,v) (left ++ [(cap,lst)]) (v2,xs) 

knapsack = foldr addItem (repeat (0, replicate numKnapsacks (capacity,[]))) 
    where addItem (name,w,v) list = left ++ zipWith max right newlist 
      where newlist = map (stuff (name,w,v) []) list 
       (left,right) = splitAt w list 

main = print $ (knapsack inv) !! 600 

OUTPUT (tổng giá trị tiếp theo khả năng của mỗi chiếc ba lô còn lại trọng lượng và nội dung):

*Main> main 
(1062,[(1,[("map",9,150),("tshirt",24,15),("trousers",42,70), 
      ("overclothes",43,75),("notecase",22,80),("sunglasses",7,20), 
      ("towel",18,12),("socks",4,50),("book",30,10)]), 
     (0,[("compass",13,35),("cheese",23,30),("cream",11,70), 
      ("camera",32,30),("trousers",48,10),("umbrella",73,40)]), 
     (1,[("sandwich",50,160),("glucose",15,60),("tin",68,45),("banana",27,60), 
      ("apple",39,40)])])