一道压榨搬砖工的动归题

有n个搬砖工，搬砖工i(1<i<=n)每天搬s[i]个转，但是要吃b[i]碗饭。现在一共需要搬m个砖，老板又希望给的饭最少，应该挑哪几个搬砖工呢？

# -*- utf-8 -*-
import numpy as np

def dp(s, b, m):
    barr = np.zeros(shape=(len(s), m)) # 最少碗饭
    sarr = np.zeros(shape=(len(s), m)) # 砖头数
    parr = list() # 搬砖工集合
    for i in range(len(s)):
        parr.append([])
        for j in range(m):
            parr[i].append(set())

    for j in range(m): # 第1行只能选搬砖工p[0]
        barr[0][j] = b[0]
        sarr[0][j] = s[0]
        parr[0][j].add(0)

    for i in range(len(s)): # 第1列选b最少的
        min_b = min(b[:i+1])
        index = b.index(min_b)

        barr[i][0] = min_b
        sarr[i][0] = s[index]
        parr[i][0].add(index)

    for i in range(len(s)):
        for j in range(m):
            if barr[i][j] != 0:
                continue
            # 砖头不达标, 则肯定要加上搬砖工
            if sarr[i-1][j] < j+1: 
                barr[i][j] = barr[i-1][j] + b[i]
                sarr[i][j] = sarr[i-1][j] + s[i]
                parr[i][j] = parr[i-1][j].union(set([i]))
            else:
                # 选用当前搬砖工
                if j+1 - s[i] > 0:
                    btmp = barr[i-1][j-s[i]] + b[i]
                    stmp = sarr[i-1][j-s[i]] + s[i]
                    ptmp = parr[i-1][j-s[i]].union(set([i]))
                else:
                    btmp = b[i]
                    stmp = s[i]
                    ptmp = set([i])
                # 选吃饭最少的
                if btmp < barr[i-1][j]:
                    barr[i][j] = btmp
                    sarr[i][j] = stmp
                    parr[i][j] = ptmp
                else:
                    barr[i][j] = barr[i-1][j]
                    sarr[i][j] = sarr[i-1][j]
                    parr[i][j] = parr[i-1][j].union(set())
    return barr, sarr, parr

if __name__ == '__main__':
    s = [10, 6, 7, 8, 9]
    b = [4, 1, 3, 4, 3]
    m = 20
    barr, sarr, parr = dp(s, b, m)
    print(barr)
    print(sarr)
    print(parr)

继续搬砖。