0-1背包问题Python 蓝桥杯备战倒计时96天

代码是自己写的 例题没有 所以输入格式上会有局限 可自行改动

#0-1背包问题
N,W=map(int,input().strip().split())#石头个数，背包限重
V=list(map(int,input().split()))#石头价值
V.insert(0,0)
w=list(map(int,input().split()))#石头价值
w.insert(0,0)

#石头重量
dp=[[0]*(N+1) for _ in range(W+1)]#dp[i][j]代表容量为i时 前j个石头的最大价值
for j in range(1,N+1):
    for i in range(0,W+1):
        if w[j]>i:
            dp[i][j]=dp[i][j-1]
        else:
            dp[i][j]=max(dp[i][j-1],dp[i-w[j]][j-1]+V[j])
print(dp[W][N])#0-1