01背包

[编程题]01背包

热度指数：6886 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

现有一个容量大小为V的背包和N件物品，每件物品有两个属性，体积和价值，请问这个背包最多能装价值为多少的物品？

输入描述:

第一行两个整数V和n。
接下来n行，每行两个整数体积和价值。1≤N≤1000,1≤V≤20000。
每件物品的体积和价值范围在[1,500]。

输出描述:

输出背包最多能装的物品价值。

示例1

输入

输出

算法知识视频讲解

Python

牛客117720058号

差1ms。。。

V, n = input().split()
V = int(V)
n = int(n)
W=[]
P=[]
for i in range(n):
    w,p = input().split()
    W.append(int(w))
    P.append(int(p))
    
def knapsack_loop():
    f = [[0 for i in range(V+1)] for j in range(n)]
    for y in range(W[n-1],V+1):
        f[n-1][y] = P[n-1]
    for i in range(n-2,-1,-1):
        for y in range(V+1):
            if y>=W[i]:
                f[i][y] = max(f[i+1][y],f[i+1][y-W[i]]+P[i])
            else:
                f[i][y] = f[i+1][y]
    return f

f=knapsack_loop()
print(f[0][V])

发表于 2023-03-11 23:38:19 回复(0)

Python

牛客45854653号

def knapsack(V , n , vw ):
    dp=[[0]*(V+1) for _ in range(n+1)]
    for i in range(1,n+1):
        vi=vw[i-1][0]
        wi=vw[i-1][1]
        for j in range(1,V+1):
            if vi>j:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-vi]+wi)
    return dp[-1][-1]
V , n =map(int,input().split())
vw=[]
for _ in range(n):
    v,w=map(int,input().split())
    vw.append([v,w])
print(knapsack(V , n , vw ))

发表于 2021-09-02 11:31:15 回复(1)