代码随想录 -- 动态规划 -- 01背包理论基础

46. 携带研究材料（第六期模拟笔试）

思路：

dp[i][j]含义：

• 在(0,i)之间任意选取物品放入容量为j的背包中，使背包的价值最大。

递推公式：

• 当前背包容纳不下第i个物品，不选第i个物品，此时背包的价值：dp[i][j]=dp[i-1][j]。
• 当前背包容纳得下第i个物品时，且选择第i个物品，此时背包的价值：dp[i][j]=dp[i-1][j-weight[i]]+value[i]；但此时dp[i][j]要取容纳价值的最大值，所以dp[i][j]=max(dp[i][j]=dp[i-1][j-weight[i]]+value[i],dp[i][j]=dp[i-1][j])

初始化：

• 从递推公式可以看出，当前元素是由其上方和左方的元素推出来的，所以要初始化第一行和第一列。
• 第一行表示背包中只放物品0，所以当 j<weight 时，dp[0][j]=0；当 j>=weight 时，dp[0][j]=weight[0]。
• 第一列表示背包容量为0，所以dp[i][0]=0。

遍历顺序：

• 从递推公式中可以看出，先遍历背包还是先遍历物品都一样。

m,n=map(int,input().split())
weight=list(map(int,input().split()))
value=list(map(int,input().split()))
dp=[[0]*(n+1) for _ in range(m)]
for j in range(n+1):
    if j>=weight[0]:
        dp[0][j]=value[0]
for i in range(1,m):
    for j in range(n+1):
        if weight[i]>j:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
print(dp[m-1][n])

注意：

python的输入函数