dp求方案 无需按照字典序排序做法

从最后一个结果的状态，反推现阶段的结果由哪个前面的结果得出,并且更新现阶段的状态（也就是体积大小）,以此从后往前依次推出每次选择的方案。

N = 20
w = [[0]*N for i in range(N)]
f = [[0]*N for i in range(N)] #f[i,j]
path = []

n,m = map(int,input().split())
for i in range(1,n+1):
    w[i][1:] = list(map(int,input().split()))

for i in range(1,n+1): #正向执行DP
    for j in range(m+1):
        f[i][j] = f[i-1][j]
        for k in range(j+1):
            f[i][j] = max(f[i][j],f[i-1][j-k]+w[i][k])

print(f[n][m])

j = m
for i in range(n,0,-1): #倒推
    for k in range(j+1):
        if f[i][j] == f[i-1][j-k]+w[i][k]:
            print(i,k)
            j-=k
            break

通过拓扑图求最短路思路得出方案做法

我们知道，动态规划实际上是对拓扑图求最短路径,这里的最短路径也即该题中的的最大价值，那么我们就可以参考最短路求方案的思想根据上一个阶段以及该阶段的关系来得出选择的方案。

N = 20
w = [[0]*N for i in range(N)]
f = [[0]*N for i in range(N)] #f[i,j]
path = []

n,m = map(int,input().split())
for i in range(1,n+1):
    w[i][1:] = list(map(int,input().split()))

def dfs(i,j):
    if (not i):return

    for k in range(j+1):
        if f[i][j] == f[i-1][j-k]+w[i][k]:
            print(i,k)
            dfs(i-1,j-k)
            return


for i in range(1,n+1):
    for j in range(m+1):
        f[i][j] = f[i-1][j]
        for k in range(j+1):
            f[i][j] = max(f[i][j],f[i-1][j-k]+w[i][k])

print(f[n][m])

dfs(n,m)

字典序做法

该题并没有要求我们通过字典序排序来做，但是如果要求我们按照字典序排序来输出结果，我们可以参考背包问题求具体方案的写法，反向执行dp，值得注意的是无论是正向dp还是反向dp，得到的最终的最大价值都是一样的，但是反向执行dp，让我们可以通过从较高的位置来转移得到较低位置的答案，那么我们就可以通过对比低端与高端之间的转移关系来思考是否选择该条路径，由于要满足字典序，所以当我们发现可以选择的时候就必须选择该条路径。

N = 20
w = [[0]*N for i in range(N)]
f = [[0]*N for i in range(N)]

n,m = map(int,input().split())
for i in range(1,n+1):
    w[i][1:] = list(map(int,input().split()))

for i in range(n,0,-1): # 反向执行DP
    for j in range(m+1):
        for k in range(j+1):
            f[i][j] = max(f[i][j],f[i+1][j-k]+w[i][k])

print(f[1][m])

j = m
res = [0]*N
for i in range(1,n+1): #倒推，由于是反向执行的，从1开始
    for k in range(j+1):
        if f[i][j]==f[i+1][j-k]+w[i][k]:
            res[i] = k
            j-=k
            break
for i in range(1,n+1):
    print(i,res[i])

DFS暴力解法

对DFS暴力的详细解释：小猫爬山

N = 20
w = [[0]*N for i in range(N)]

n,m = map(int,input().split())
for i in range(1,n+1):
    w[i][1:] = list(map(int,input().split()))

maxv = 0
res = []
def dfs(u,sums,cnt,v):
    global maxv,res

    if (u>n):
        if sums>maxv:
            maxv = sums
            res = v.copy()
        return

    for i in range(cnt+1):
        v.append(i)
        dfs(u+1,sums+w[u][i],cnt-i,v)
        v.pop()

dfs(1,0,m,[0])

print(maxv)
for i in range(1,n+1):
    print(i,res[i])