我要招人

去企业版

首页 > 试题广场 >

【模板】01背包

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

热度指数：23698 时间限制：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

颜星河

import sys

n, V = map(int, sys.stdin.readline().split())
items = []
for line in sys.stdin:
    items.append(tuple(map(int, line.split())))

dp1 = [[0 for _ in range(V + 1)] for _ in range(n + 1)]
dp2 = [[0 for _ in range(V + 1)] for _ in range(n + 1)]

for i in range(1, n + 1):
    v_i, w_i = items[i - 1]
    for j in range(0, V + 1):
        dp1[i][j] = dp1[i - 1][j]
        dp2[i][j] = dp2[i - 1][j]
        if j >= v_i:
            dp1[i][j] = max(dp1[i][j], dp1[i - 1][j - v_i] + w_i)
            if j == v_i&nbs***bsp;dp2[i - 1][j - v_i] != 0:
                dp2[i][j] = max(dp2[i][j], dp2[i - 1][j - v_i] + w_i)

print(dp1[n][V])
print(dp2[n][V])

发表于 2025-04-19 11:58:50 回复(0)

Python3

牛客242804485号

import sys

from math import inf

v = []

w = []

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

for i in range(n):

x, y = map(int, input().split())

v.append(x)

w.append(y)

f = [[0]*(V+1) for _ in range(n+1)]

f2 = [[-inf]*(V+1) for _ in range(n+1)]

f[1][0] = 0

f2[0][0] = 0

for i in range(n):

for j in range(V+1):

if j < v[i]:

f[i+1][j] = f[i][j]

f2[i+1][j] = f2[i][j]

else:

f[i+1][j] = max(f[i][j],f[i][j-v[i]]+w[i])

f2[i+1][j] = max(f2[i][j],f2[i][j-v[i]]+w[i])

ans = f[n][V]

ans2 = f2[n][V]

if ans2 < 0:

ans2 = 0

print(ans)

print(ans2)

发表于 2025-04-05 14:59:26 回复(0)

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)