首页 > 试题广场 >

【模板】01背包

[编程题]【模板】01背包
  • 热度指数：19779 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
你有一个背包，最多能容纳的体积是V。

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

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

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




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

示例1

输入

3 5
2 10
4 5
1 4

输出

14
9

说明

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

输入

3 8
12 6
11 8
6 8

输出

8
0

说明

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

备注:
要求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条回答 1629浏览

热门推荐

通过挑战的用户

查看代码

相关试题

【模板】01背包

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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