+寻找动态规划值和权重+

Question

+++
下表列出了三个城市的无家可归者人数，其中要建造的房屋数量。你知道吗

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

我们追求的是一种住房策略，即尽量减少住房总数量 所有3个城市的无家可归者都有一定数量的住房。
向无家可归者提供的n住房的最佳分配是什么？总共会有多少无家可归者？
解决方案是采用动态编程&be in Python。
它看起来像一个容量n的无界背包问题，但很难找到用作算法参数的值和权重。
请分享您的观点。
+++你知道吗

Answer 1

+++
我已经设法解决了一个有界背包的情况下，有多个值的任务如下。你知道吗

---

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])

++++