首页 > 试题广场 >

【模板】01背包

[编程题]【模板】01背包
  • 热度指数：26079 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}你有一个背包，最大容量为 V。现有 n 件物品，第 i 件物品的体积为 v_i，价值为 w_i。研究人员提出以下两种装填方案：
{\hspace{20pt}}_\texttt{1.}\, 不要求装满背包，求能获得的最大总价值；
{\hspace{20pt}}_\texttt{2.}\, 要求最终恰好装满背包，求能获得的最大总价值。若不存在使背包恰好装满的装法，则答案记为 0。

输入描述:
\hspace{15pt}第一行输入两个整数 n 和 V\left(1\leqq n,V\leqq 10^3\right)，分别表示物品数量与背包容量。 
\hspace{15pt}此后 n 行，第 i 行输入两个整数 v_i, w_i\left(1\leqq v_i,w_i\leqq 10^3\right)，分别表示第 i 件物品的体积与价值。


输出描述:
\hspace{15pt}输出两行： 
{\hspace{20pt}}_\texttt{1.}\, 第一行输出方案 \texttt{1} 的答案； 
{\hspace{20pt}}_\texttt{2.}\, 第二行输出方案 \texttt{2} 的答案（若无解输出 0）。
示例1

输入

3 5
2 10
4 5
1 4

输出

14
9

说明

\hspace{15pt}在该组样例中： 
\hspace{23pt}\bullet\, 选择第 1、第 3 件物品即可获得最大价值 10+4=14（未装满）； 
\hspace{23pt}\bullet\, 选择第 2、第 3 件物品可使背包体积 4+1=5 恰好装满且价值最大，为 5+4=9。
示例2

输入

3 8
12 6
11 8
6 8

输出

8
0

说明

\hspace{15pt}装第三个物品时总价值最大但是不满，装满背包无解。

备注:
\hspace{15pt}要求 O(nV) 的时间复杂度，O(V) 空间复杂度。
算法知识视频讲解
添加回答
Python3
老宋头头像 老宋头 
n,v = map(int,input().split())
vm = []
for i in range(0,n):
    vm.append(list(map(int,input().split())))
dp = [[0 for _ in range(v+1)] for _ in range(n)]
dpp = [[-float('inf')]*(v+1) for _ in range(n)]
dpp[0][0]=0
for i in range(0,v+1):
    if vm[0][0]<=i:
        dp[0][i] = vm[0][1]
    if vm[0][0] ==i :
        dpp[0][i] = vm[0][1]
for i in range(1,n):
    for j in range(1,v+1):
        if vm[i][0]>j:
            dp[i][j] = dp[i-1][j]
            dpp[i][j] = dpp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-vm[i][0]]+vm[i][1])
            dpp[i][j] = max(dpp[i-1][j],vm[i][1]+dpp[i-1][j-vm[i][0]] if dpp[i-1][j-vm[i][0]]!=-float('inf') else -float('inf'))
        
print(dp[n-1][v])
print(dpp[n-1][v] if dpp[n-1][v]!=-float('inf') else 0)
这个代码有什么问题啊，
发表于 2025-05-26 23:20:11 回复(0)
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号头像 牛客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号头像 牛客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)
提交观点

问题信息

难度：
4条回答 2196浏览

热门推荐

通过挑战的用户

查看代码

相关试题

【模板】01背包

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号