首页 > 试题广场 >

【模板】01背包

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

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

输入描述:

第一行输入两个整数  和 ，分别表示物品数量与背包容量。 
此后  行，第  行输入两个整数 ，分别表示第  件物品的体积与价值。

输出描述:

输出两行： 
 第一行输出方案  的答案； 
 第二行输出方案  的答案（若无解输出 ）。

示例1

输入

输出

14
9

说明

在该组样例中： 
 选择第 、第  件物品即可获得最大价值 （未装满）； 
 选择第 、第  件物品可使背包体积  恰好装满且价值最大，为 。

示例2

输入

输出

8
0

说明

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

备注:

要求  的时间复杂度， 空间复杂度。

算法知识视频讲解

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号

补个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)