Drukowanie Przedmioty znajdujące się w worku w plecaku

Question

Załóżmy, że jesteś złodziejem i zaatakowałeś dom. W środku znalazłeś następujące przedmioty:

Wazon, który waży 3 funty i jest wart 50 dolarów.
Srebrzysty samorodek, który waży 6 funtów i jest wart 30 dolarów.
Obraz, który waży 4 funty i jest wart 40 dolarów.
Lustro, które waży 5 funtów i jest warte 10 dolarów.

Rozwiązanie tego problemu z plecakiem o wadze 10 funtów to 90 dolarów.

stołowy wykonany z programowania dynamicznego jest: -

Teraz chcę wiedzieć, które elementy i umieścić w worku za pomocą tej tabeli to jak BackTrack ??

Answer 1

Z tabeli DP wiemy, że f [i] [w] = maksymalna łączna wartość podzbioru pozycji 1..i o łącznej wadze mniejszej lub równej w.

Możemy użyć samej tabeli, aby przywrócić optymalną pakowanie:

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

za pomocą pętli:

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

mam iteracyjny algorytm inspirowany @NiklasB. działa, gdy algorytm rekurencyjny osiągnie pewien limit rekursji.

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