【模板】01背包

[编程题]【模板】01背包

热度指数：20745 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为 $v_i$ ,价值为 $w_i$ 。

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述:

第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数和，表示第i个物品的体积和价值。

输出描述:

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1

输入

输出

14
9

说明

装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。

示例2

输入

输出

8
0

说明

装第三个物品时总价值最大但是不满，装满背包无解。

备注:

要求O(nV)的时间复杂度，O(V)空间复杂度

算法知识视频讲解

Python3

牛客253248209号

# 先记录一下第一个问题的答案

n,w = map(int,input().split())

# 构造装进去
lv,lw=[],[]
for i in range(n):
l= list(map(int,input().split()))
lv.append(l[0])
lw.append(l[1])
dp=[[0 for i in range(w+1)] for i in range(n+1)]
lv.insert(0,0)
lw.insert(0,0)
# 然后进行循环
for i in range(1,n+1):
for j in range(1,w+1):
if lv[i]<j:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-lv[i]]+lw[i])
else:
dp[i][j] = dp[i-1][j]
print(dp[n][w])

发表于 2022-08-23 23:25:24 回复(0)