我要招人

去企业版

首页 > 试题广场 >

01背包

[编程题]01背包

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

已知一个背包最多能容纳体积之和为v的物品

现有 n 个物品，第 i 个物品的体积为 v_i , 重量为 w_i

求当前背包最多能装多大重量的物品?

数据范围： $1 \le v \le 1000$ ， $1 \le n \le 1000$ ， $1 \le v_i \le 1000$ ， $1 \le w_i \le 1000$

进阶： $O(n \cdot v)$

示例1

输入

10,2,[[1,3],[10,4]]

输出

说明

第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为4

示例2

输入

10,2,[[1,3],[9,8]]

输出

说明

两个物品体积之和等于背包能装的体积，所以两个物品都取是最优方案

算法知识视频讲解

Python 3

小飞mm

python用第一种初始化dp矩阵，总是把同一列的数值全部初始化有人知道怎么回事吗？

dp = [[0] * (V+1)] * n

dp = [[0 for _ in range(V+1)] for _ in range(n)]

for i in range(vw[0][0], V+1):
dp[0][i] = vw[0][1]

发表于 2022-02-17 19:51:32 回复(0)

Python 3

HHHChen77

# 为啥我怎么写都会超时卡在17/20

python 二维dp

#
class Solution:
    def knapsack(self , V , n , vw ):
        # 经典问题 0/1背包
        # 动态规划 dp[i][j]定义为面对前i个物品体积为j背包能装下的最大重量
        dp = [[0]*(V+1) for _ in range(n+1)]
        # 状态转移
        for i in range(1, n+1):
            for j in range(1, V+1):
                # 拿
                dp[i][j] = dp[i-1][j]
                # 不拿
                if j >= vw[i-1][0]:
                    dp[i][j] = max(dp[i][j], dp[i-1][j-vw[i-1][0]]+vw[i-1][1])
        # 计算最终能装下的最大重量
        return dp[n][V]

python 一维dp（空间优化）

class Solution:
    def knapsack(self , V , n , vw ):
        # 经典问题 0/1背包
        # 动态规划 dp[j]定义为体积j背包能装下的最大重量
        dp = [0]*(V+1)
        # 状态转移
        for i in range(1, n+1):
            for j in range(V, 0, -1):
                # 面对第i个物品,判断能不能拿
                if j >= vw[i-1][0]:
                    dp[j] = max(dp[j], dp[j-vw[i-1][0]]+vw[i-1][1])
        # 计算最终能装下的最大重量
        return dp[V]

发表于 2021-08-11 14:26:14 回复(0)

Python 3

OswaldWang

为什么我总是超时？只能过 19/20。基本的01背包问题，写的和python3通过的也没什么区别啊。为什么我的总是超时，别人的25ms？

class Solution:
    def knapsack(self , V , n , vw ):
        # write code here
        dp = [0] * (V+1)
        for i in range(n):
            vi = vw[i][0]
            wi = vw[i][1]
            for j in range(V, vi-1, -1):
                if dp[j] >= dp[j-vi] + wi:
                    continue
                else:
                    dp[j] = dp[j-vi] + wi

        return dp[V]

发表于 2021-08-04 00:02:53 回复(0)

Python 3

牛客35961088号

class Solution:
    def knapsack(self , V , n , vw ):
        # write code here
        dp = [[0 for _ in range(V+1)] for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, V+1):
                if j < vw[i-1][0]:
                    dp[i][j] = dp[i-1][j]        # 当前体积不装第i个物品
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-vw[i-1][0]]+vw[i-1][1])
                    # # 当前体积不装第i个物品 或者 之前的体积+新装物体的价值
        return dp[n][V]

发表于 2021-07-30 22:24:39 回复(0)