In ấn Các vật phẩm đang ở trong bao trong knapsack

Question

Giả sử bạn là kẻ trộm và bạn đã xâm chiếm một ngôi nhà. Bên trong, bạn tìm thấy các mục sau:

Bình có trọng lượng 3 pound và trị giá 50 đô la.
Một nugget bạc có trọng lượng 6 pound và trị giá 30 đô la.
Một bức tranh có trọng lượng 4 pound và đáng giá 40 đô la.
Một chiếc gương có trọng lượng 5 pound và trị giá 10 đô la.

Giải pháp cho vấn đề Knapsack có kích thước 10 pound này là 90 đô la.

Bảng làm từ lập trình năng động là: -

Bây giờ tôi muốn biết những yếu tố tôi đặt trong túi của tôi sử dụng bảng này sau đó làm thế nào để sao lưu theo dõi ??

Answer 1

Từ bảng DP của bạn, chúng tôi biết f [i] [w] = tổng giá trị tối đa của một tập con của các mục 1..i có tổng trọng số nhỏ hơn hoặc bằng w.

Chúng ta có thể sử dụng bảng riêng của mình để khôi phục lại đóng gói tối ưu:

def reconstruct(i, w): # reconstruct subset of items 1..i with weight <= w 
         # and value f[i][w] 
    if i == 0: 
     # base case 
     return {} 
    if f[i][w] > f[i-1][w]: 
     # we have to take item i 
     return {i} UNION reconstruct(i-1, w - weight_of_item(i)) 
    else: 
     # we don't need item i 
     return reconstruct(i-1, w) 

Answer 2

Sử dụng một vòng lặp:

for (int n = N, w = W; n > 0; n--) 
      { 
       if (sol[n][w] != 0) 
       { 
        selected[n] = 1; 
        w = w - wt[n]; 
       } 
       else 
        selected[n] = 0; 
      } 
      System.out.print("\nItems with weight "); 
      for (int i = 1; i < N + 1; i++) 
       if (selected[i] == 1) 
        System.out.print(val[i] +" "); 

Answer 3

Tôi có một thuật toán lặp lấy cảm hứng từ @NiklasB. hoạt động khi một thuật toán đệ quy sẽ nhấn một số loại giới hạn đệ quy.

def reconstruct(i, w, kp_soln, weight_of_item): 
    """ 
    Reconstruct subset of items i with weights w. The two inputs 
    i and w are taken at the point of optimality in the knapsack soln 

    In this case I just assume that i is some number from a range 
    0,1,2,...n 
    """ 
    recon = set() 
    # assuming our kp soln converged, we stopped at the ith item, so 
    # start here and work our way backwards through all the items in 
    # the list of kp solns. If an item was deemed optimal by kp, then 
    # put it in our bag, otherwise skip it. 
    for j in range(0, i+1)[::-1]: 
     cur_val = kp_soln[j][w] 
     prev_val = kp_soln[j-1][w] 
     if cur_val > prev_val: 
      recon.add(j) 
      w = w - weight_of_item[j] 
    return recon