+ Finding Dynamische Programmierung Werte & Gewichte +

Question

+++
Wir sind in der folgenden Tabelle über die Zahl der Obdachlosen in jeder der drei Städte gegeben, wobei n die Zahl der Haushalte gebaut werden.

 
City n=0 n=1 n=2 
A  15 12 10 
B  9 8 4 
C  8 6 5 

Wir sind nach einer Gehäuse-Strategie, die die Gesamtzahl der Obdachlose in allen drei Städten für eine bestimmte Anzahl von Häusern minimiert.
Was wäre die optimale Zuteilung von n Häuser zu obdachlos, und wie viele Obdachlose würde das Ergebnis insgesamt?
Die Lösung besteht darin, dynamische Programmierung & in Python zu verwenden.
Es scheint wie ein unbegrenztes Rucksackproblem mit der Kapazität n aber was schwer zu finden sind die Werte & Gewichtungen als Parameter des Algorithmus verwendet werden.
Bitte teilen Sie Ihre Ansichten.
+++

Answer 1

+++
Ich habe es geschaffen mit mehreren Werten die Aufgabe als beschränkten Tornister Fall wie folgt zu lösen.

---

def assign_home(cpct, tbl): 
    ctNum = len(tbl[0]) 
    wghts = [1] * ctNum 
    vls = get_vls(tbl) 
    hms = [0] * ctNum 
    HMSBND = 2 
    hmlsVal = [sum(row[0] for row in tbl) for hmIndx in range(min(cpct + 1, ctNum * HMSBND + 1))] 
    for hmIndx in range(min(wghts), min(cpct + 1, ctNum * HMSBND + 1)): 
     chsn = -1 
     for ct, wght in enumerate(wghts): 
      if wght <= hmIndx and hms[ct] < HMSBND and hmlsVal[hmIndx] > hmlsVal[hmIndx - wght] - vls[ct][hms[ct]]: 
       hmlsVal[hmIndx] = hmlsVal[hmIndx - wght] - vls[ct][hms[ct]] 
       chsn = ct 
     if chsn != -1: 
      hms[chsn] += 1 
    return hmlsVal[min(cpct, ctNum * HMSBND)], hms 

def get_vls(tbl): 
    [A, B, C] = tbl 
    Adf = [A[0] - A[1], A[1] - A[2]] 
    Bdf = [B[0] - B[1], B[1] - B[2]] 
    Cdf = [C[0] - C[1], C[1] - C[2]] 
    return [Adf, Bdf, Cdf] 

tbl=[[15, 12, 10], [9, 8, 4], [8, 6, 5]] 
print(assign_home(5, tbl)) 
# (20, [2, 2, 1]) 

+++