首页 > 试题广场 >

【模板】01背包

[编程题]【模板】01背包
  • 热度指数：26834 时间限制：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) 空间复杂度。
算法知识视频讲解
添加回答
Python 3
神圣之风头像 神圣之风
import sys
def solution():
    input=sys.stdin.readlines()
    frst_line=[eval(i) for i in input[0].strip().split(" ")]
    num_obj,vol_total=frst_line
    data=[i.strip().split(" ") for i in input[1:]]
    for i in range(0,len(data)):
        data[i]=[eval(j) for j in data[i]]
    #构造DP矩阵
    mat=[[0 for i in range(0,vol_total+1)] for j in range(num_obj+1)]
    for i in range(1,num_obj+1):
        for j in range(0,vol_total+1):
            if(data[i-1][0]>j):
                mat[i][j]=mat[i-1][j]                #如果不能装载obj的话，就直接用上一行的值;注意是大于，不能等于
            else:
                mat[i][j]=max(mat[i-1][j],data[i-1][1]+mat[i-1][j-data[i-1][0]])
    answer1=mat[-1][-1]
    print(answer1)
    #构造DP矩阵
    mat=[[float('-inf') for i in range(0,vol_total+1)] for j in range(num_obj+1)]
    mat[0][0]=0
    for i in range(1,num_obj+1):
        for j in range(0,vol_total+1):
            if(data[i-1][0]>j):
                mat[i][j]=mat[i-1][j]                #如果不能装载obj的话，就直接用上一行的值
            else:
                mat[i][j]=max(mat[i-1][j],data[i-1][1]+mat[i-1][j-data[i-1][0]])
    answer2=mat[-1][-1] if mat[-1][-1]!=float('-inf') else 0 
    #print(mat)
    print(answer2)
solution()
发表于 2022-06-26 23:17:39 回复(0)
Python 3
牛客760622808号头像 牛客760622808号
补个python的 
def ans():
    n, v = map(int, input().split(" "))
    size , worth = [0 for _ in range(n)]  , [0 for _ in range(n)]
    for i in range(n):
        size[i] , worth[i] = map(int, input().split(" "))
    
    dp1 = [0 for _ in range(v+1)]
    dp2 = [float("-inf") for _ in range(v+1)]
    dp2[0] = 0

    for i in range(n):
        for j in range(v,0,-1):
            if j >= size[i]:
                dp1[j] = max(dp1[j - size[i]] + worth[i] , dp1[j])
                dp2[j] = max(dp2[j - size[i]] + worth[i] , dp2[j])
    
    print(dp1[-1])
    res = 0 if dp2[-1] == float("-inf") else dp2[-1]
    print(res)

ans()


发表于 2021-11-03 16:55:38 回复(0)
提交观点

问题信息

难度：
3条回答 2350浏览

热门推荐

通过挑战的用户

查看代码

相关试题

【模板】01背包

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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