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

Question

+++
我们得到以下 3 个城市中无家可归者人数的 table，其中 n 待建房屋的数量。

城市 n=0 n=1 n=2
 15 12 10
 乙 9 8 4
 C 8 6 5

我们正在寻求一种住房策略，该策略可以最大限度地减少总人数给定数量的房屋中所有 3 个城市的无家可归者。
将 n 个房屋分配给无家可归者的最佳分配是多少，这将导致总共有多少无家可归者？
解决方案是采用动态规划并处于 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])

+++

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

+Finding Dynamic Programming Values & Weights+

python

algorithm

knapsack-problem

dynamic-programming