蓝桥 python笔记13——01背包、完全背包、多重背包、二维费用背包、分组背包

目录

01背包

完全背包

多重背包

二维费用背包

分组背包

01背包

N,V=map(int,input().split())
#dp[N][V]表示N数量和V容积下，背包的价值最大值
dp=[[0]*(V+1) for _ in range(N+1)]

for i in range(1,N+1):
    wi,vi=map(int,input().split())
    for j in range(0,V+1):
        if j<wi:
           dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-wi]+vi)
print(dp[N][V])

滚动数组优化：

N,V=map(int,input().split())
dp=[0]*(V+1)

for i in range(1,N+1):
  w,v=map(int,input().split())
  #当j小于w时，放不下当前的物品，所以无需更新
  for j in range(V,w-1,-1):
    dp[j]=max(dp[j],dp[j-w]+v)
print(dp[V])

完全背包

N,V=map(int,input().split())
dp=[[0]*(V+1) for _ in range(N+1)]

for i in range(1,N+1):
    wi,vi=map(int,input().split())
    for j in range(0,V+1):
        if j<wi:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-wi]+vi)
print(dp[N][V])

N,V=map(int,input().split())
dp=[0]*(V+1)

for i in range(1,N+1):
  w,v=map(int,input().split())
  #当j小于w时，放不下当前的物品，所以无需更新
  for j in range(w,V+1):
    dp[j]=max(dp[j],dp[j-w]+v)
print(dp[V])

多重背包

二维费用背包

#N是数量，V是容积，M是质量
N,V,M=map(int,input().split())
#滚动数组是：dp[V][M]
dp=[[0]*(M+1) for _ in range(V+1)]

for i in range(1,N+1):
    # vi体积，mi重量，wi价值
    vi,mi,wi=map(int,input().split())
    # 体积为j，从大到小
    for j in range(V,vi-1,-1):
        #重量为k，从大到小
        for k in range(M,mi-1,-1):
            #dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-vi][k-mi]+wi)
            dp[j][k]=max(dp[j][k],dp[j-vi][k-mi]+wi)
print(dp[V][M])

分组背包