完全背包

[编程题]完全背包

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

你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为 $v_i$ ,价值为 $w_i$ 。

（1）求这个背包至多能装多大价值的物品？

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

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

示例1

输入

6,2,[[5,10],[3,1]]

输出

[10,2]

示例2

输入

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

输出

[20,0]

说明

无法恰好装满背包。

示例3

输入

13,6,[[13,189],[17,360],[19,870],[14,184],[6,298],[16,242]]

输出

[596,189]

说明

可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.

算法知识视频讲解

Python3

__龙舌兰日落

python版本简单解法，只需要维护一个dp数组就好。

加一个判断条件，判断如果当前位置dp[i] = 0（没有放物品），则不进行累计。

class Solution:
    def knapsack(self , v: int, n: int, nums: List[List[int]]) -> List[int]:
        dp = [0]*(v+1)
        for i in range(n):
            for j in range(0, v - nums[i][0]+1): # 完全背包问题，正向遍历容量
                if dp[j] != 0&nbs***bsp;j == 0:
                    dp[j+ nums[i][0]] = max(dp[j+ nums[i][0]], dp[j] + nums[i][1])
        return [max(dp), dp[v]]

发表于 2023-03-19 16:38:55 回复(0)