我们今天来学习完全背包问题，完全背包问题是基于0-1背包的基础，如果不明白或者忘记了可以点击下面的链接。

https://blog.csdn.net/qq_53500156/article/details/123454958?spm=1001.2014.3001.5501

 为什么呢，0-1背包问题，它是按照前一行来进行计算，而完全背包问题就可以在该行进行判断与计算。好好理解

c = 10          #背包容量
w = [3,4,5,7]   #物体体积
v = [1,5,6,9]   #物体的价值
n = len(w)
dp = [[0 for i in range(c+1)]for j in range(1+n)]  #创建一个n*c的零矩阵
w.insert(0,0)  #因为dp表上次和左侧各有一列0，为了索引对齐
v.insert(0,0)  #在0位置加个0，相当于在v的0位置加个0 ，即1前加0
for i in range(1,n+1):
    for j in range(1,c+1):
        if w[i] <= j:       #物体体积小于背包体积时，有两种情况：
#要么是前一个装完最大，要么是装完现在这个还可以装其他的。
            dp[i][j] = max (dp[i-1][j],dp[i][j-w[i]] + v[i])  #与0-1不同的点就在这里
        else:
            dp[i][j] = dp[i-1][j]
print("最大价值为",dp[n][c])
      

我们知道，0-1背包有路径，我们完全背包也得有路径才行。

 这完全是一样的，就是我们从后面往前推，不需要前一行的值。

c = 10                      #背包容量
w = [3,4,5,7]               #物体体积
v = [1,5,6,9]               #物体的价值
n = len(w)
dp = [[0 for i in range(c+1)]for j in range(1+n)]  #创建一个n*c的零矩阵
w.insert(0,0)               #因为dp表上次和左侧各有一列0，为了索引对齐
v.insert(0,0)               #在0位置加个0，相当于在v的0位置加个0 ，即1前加0
for i in range(1,n+1):
    for j in range(1,c+1):
        if w[i] <= j:       #物体体积小于背包体积时，有两种情况：
#要么是前一个装完最大，要么是装完现在这个还可以装其他的。
            dp[i][j] = max (dp[i-1][j],dp[i-1][j-w[i]] + v[i])
        else:
            dp[i][j] = dp[i-1][j]
print("最大价值为",dp[n][c])

def get_path(dp,w,c):
    i = len(w)-1            #选中的物体
    j = c                   #背包的容量
    res = []
    while i != 0 and j != 0:  #上面的dp表0行和0列都等于0，所以我们只要索引到它即可
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        else:
            res.append(i-1) #上边w,v都加了0，索引的时候减一，不然会出现0，会误导结果
            j -= w[i]       #背包面积减去装的物体，得到那时的背包体积
    res.sort()
    return res
print("背包物品索引为",get_path(dp,w,c))